Cycles with two blocks in k‐chromatic digraphs. Issue 4 (12th December 2017)

• Record Type: Journal Article
• Authors: Kim, Ringi; Kim, Seog‐Jin; Ma, Jie; Park, Boram
• Is Part Of: Journal of graph theory. Volume 88:Issue 4(2018)
• Page Start: 592
• Page End: 605
• Publication Date: 2017-12-12
• Subjects: chromatic number -- cycle with two blocks -- digraph coloring -- strongly connected digraph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22232
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: Let k and ℓ be positive integers. A cycle with two blocks c ( k, ℓ ) is a digraph obtained by an orientation of an undirected cycle, which consists of two internally (vertex) disjoint paths of lengths at least k and ℓ, respectively, from a vertex to another one. A problem of Addario‐Berry, Havet and Thomassé [ J. Combin. Theory Ser. B 97 (2007), 620–626] 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 article, we show that such digraph D has chromatic number at most O ( ( k + ℓ ) 2 ), improving the previous upper bound O ( ( k + ℓ ) 4 ) of Cohen et al. [ Subdivisions of oriented cycles in digraphs with large chromatic number, to appear]. 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.