2016/10/19 by Ringi Kim, Seog‐Jin Kim, Kim, Ringi +5 · 1 citation
Computer Science · Mathematics · #05C15 #05C20 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1610.05839
openalex publication_date 2016/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let k and ℓ be positive integers. A cycle with two blocks c(k,ℓ) is an oriented cycle which consists of two internally (vertex) disjoint directed paths of lengths at least k and ℓ, respectively, from a vertex to another one. A problem of Addario-Berry, Havet and Thomassé (2007) asked if, given positive integers k and ℓ such that k+ℓ≥ 4, any strongly connected digraph D containing no c(k,ℓ) has chromatic number at most k+ℓ-1. In this paper, we show that such digraph D has chromatic number at most O((k+ℓ)2), improving the previous upper bound O((k+ℓ)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+ℓ-1)-degenerate and thus the chromatic number of D is at most k+ℓ, which is tight.