Cycles with two blocks in k-chromatic digraphs

Abstract

Let k and ℓ be positive integers. A cycle with two blocks c(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 Thomassé [J. Combin. Theory Ser. B 97 (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 et al. [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.