Cycles with two blocks in $k$-chromatic digraphs

Abstract

Let $k$ and $\ell$ be positive integers. A cycle with two blocks $c(k,\ell )$ is an oriented cycle which consists of two internally (vertex) disjoint directed paths of lengths at least $k$ and $\ell$, respectively, from a vertex to another one. A problem of Addario-Berry, Havet and Thomassé (2007) asked if, given positive integers $k$ and $\ell$ such that $k+\ell \ge 4$, any strongly connected digraph $D$ containing no $c(k,\ell )$ has chromatic number at most $k+\ell -1$. In this paper, we show that such digraph $D$ has chromatic number at most $O((k+\ell {)}^2)$, improving the previous upper bound $O((k+\ell {)}^4)$ obtained by Cohen, Havet, Lochet and Nisse (2016). In fact, we are able to find a digraph which shows that the answer to the above problem is no. We also show that if in addition $D$ is Hamiltonian, then its underlying simple graph is $(k+\ell -1)$-degenerate and thus the chromatic number of $D$ is at most $k+\ell$, which is tight.

16 pages, 6 figures