Two-block cycles and chromatic number of Hamiltonian digraphs

Let $k$ and $\ell$ be positive integers.

The family $C(k,\ell)$ consists of all digraphs obtained from two internally vertex-disjoint directed paths of lengths at least $k$ and $\ell$, respectively, and identifying their initial vertices and their terminal vertices.

Addario-Berry, Havet and Thomassé (JCT-B, 2007) asked whether, for any positive integers $k$ and $\ell$ with $k+\ell \ge 4$, the chromatic number $\chi(D)$ is at most $k+\ell-1$ for every $C(k,\ell)$-free strongly connected digraph $D$.

Let $D$ be a $C(k,\ell)$-free Hamiltonian digraph.

Kim, Kim, Ma and Park (JGT, 2018) showed that $\chi(D) \le k+\ell$ and the bound is attained when $k+\ell=5$.

In this paper, we prove that $\chi(D) \le k+\ell-1$ for $k+\ell\ge 6$ and this bound is best possible for all $k+\ell\geq 6$, which resolves the problem posed by Addario-Berry, Havet and Thomassé for Hamiltonian digraphs.