Cycles with two blocks in k-chromatic digraphs

Abstract

Let k and be positive integers. A cycle with two blocksc(k,) is a digraph obtained by an orientation of an undirected cycle, which consists of two internally (vertex) disjoint paths of lengths at least k and , respectively, from a vertex to another one. A problem of Addario-Berry, Havet and Thomasse [J. Combin. Theory Ser. B97 (2007), 620-626] asked if, given positive integers k and such that k+4, any strongly connected digraph D containing no c(k,) has chromatic number at most k+-1. In this article, we show that such digraph D has chromatic number at most O((k+)2), improving the previous upper bound O((k+)4) of Cohen etal. [Subdivisions of oriented cycles in digraphs with large chromatic number, to appear]. We also show that if in addition D is Hamiltonian, then its underlying simple graph is (k+-1)-degenerate and thus the chromatic number of D is at most k+, which is tight.