Subdivisions of oriented cycles in Hamiltonian digraphs with small chromatic number.

Cohen et al. conjectured that, for each oriented cycle C , there exists an integer f (C) such that any f (C) -chromatic strong digraph contains a subdivision of C as a subdigraph. In the same paper, Cohen et al. proved this conjecture for cycles with two blocks by showing that the chromatic number of strong digraphs that include no subdivision of a cycle with two blocks, with lengths of k 1 and k 2 , is bounded from above by O ((k 1 + k 2) 4). More recently, Kim et al. improved this upper bound to O ((k 1 + k 2) 2) for the class of strong digraphs and to O (k 1 + k 2) for the class of Hamiltonian digraphs. In this paper, we confirm Cohen et al.'s conjecture for Hamiltonian digraphs. We demonstrate a stronger version by showing that every 3 n -chromatic Hamiltonian digraph contains a subdivision for every oriented cycle of order n. [ABSTRACT FROM AUTHOR]