Two-block cycles and chromatic number of Hamiltonian digraphs

Abstract

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 \ge 6$, which resolves the problem posed by Addario-Berry, Havet and Thomassé for Hamiltonian digraphs.