zbMATH — the first resource for mathematics

Cycles with two blocks in \(k\)-chromatic digraphs. (English) Zbl 1393.05118
Summary: Let \(k\) and \(\ell\) be positive integers. A cycle with two blocks \((k,\ell)\) 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 \(\ell\), respectively, from a vertex to another one. A problem of L. Addario-Berry et al. [J. Comb. Theory, Ser. B 97, No. 4, 620–626 (2007; Zbl 1119.05049)] asked if, given positive integers \(k\) and \(\ell\) such that \(k+\ell \geq 4\), any strongly connected digraph \(D\) containing no \(c(k,\ell)\) has chromatic number at most \(k+\ell-1\). In this article, we show that such digraph \(D\) has chromatic number at most \(O((k+\ell)^2)\), improving the previous upper bound \(O((k+\ell)^4)\) of N. Cohen et al. [“Subdivisions of oriented cycles in digraphs with large chromatic number”, Preprint, arXiv:1605.07762]. We also show that if in addition \(D\) is Hamiltonian, then its underlying simple graph is \((k+\ell-1)\)-degenerate and thus the chromatic number of \(D\) is at most \(k+\ell\), which is tight.

05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments
05C40 Connectivity
Full Text: DOI arXiv