# 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.

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