About subdivisions of four blocks cycles $C(k_1,1,k_3,1)$ in digraphs with large chromatic number

Abstract

A cycle with four blocks $C(k_1,k_2,k_3,k_4)$ is an oriented cycle formed of four blocks of lengths $k_1,k_2,k_3$ and $k_4$ respectively. Recently, Cohen et al. conjectured that for every positive integers $k_1,k_2,k_3,k_4$, there is an integer $g(k_1,k_2,k_3,k_4)$ such that every strongly connected digraph $D$ containing no subdivisions of $C(k_1,k_2,k_3,k_4)$ has a chromatic number at most $g(k_1,k_2,k_3,k_4)$. This conjecture is confirmed by Cohen et al. for the case of $C(1,1,1,1)$ and by Al-Mniny for the case of $C(k_1,1,1,1)$. In this paper, we affirm Cohen et al.'s conjecture for the case where $k_2=k_4=1$, namely $g(k_1,1,k_3,1)=O({(k_1+k_3)}^2)$. Moreover, we show that if in addition $D$ is Hamiltonian, then the chromatic number of $D$ is at most $6k$, with $k=\text{max}\{k_1,k_3\}.$

23 pages