Cycles with two blocks in k‐chromatic digraphs

Authors:
Publisher website
Google Scholar
Abstract
Let k and ℓ be positive integers. A cycle with two blocks 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 , any strongly connected digraph D containing no has chromatic number at most . In this article, we show that such digraph D has chromatic number at most , improving the previous upper bound 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 ‐degenerate and thus the chromatic number of D is at most , which is tight.
Funding Information
  • National Research Foundation (NRF-2017R1A2B4005020)
  • Ministry of Education (NRF-2015R1D1A1A01057008)
  • National Natural Science Foundation of China (11501539, 11622110)
  • National Research Foundation of Korea
  • Ministry of Science, ICT and Future Planning (NRF-2015R1C1A1A01053495)

This publication has 11 references indexed in Scilit: