# zbMATH — the first resource for mathematics

Subdivisions of oriented cycles in digraphs with large chromatic number. (English) Zbl 06997246
Summary: An oriented cycle is an orientation of a undirected cycle. We first show that for any oriented cycle $$C$$, there are digraphs containing no subdivision of $$C$$ (as a subdigraph) and arbitrarily large chromatic number. In contrast, we show that for any $$C$$ a cycle with two blocks, every strongly connected digraph with sufficiently large chromatic number contains a subdivision of $$C$$. We prove a similar result for the antidirected cycle on four vertices (in which two vertices have out-degree 2 and two vertices have in-degree 2).

##### MSC:
 05C20 Directed graphs (digraphs), tournaments 05C38 Paths and cycles 05C15 Coloring of graphs and hypergraphs
##### Keywords:
coloring; digraph; subdivision
Full Text: