Subdivisions of oriented cycles in digraphs with large chromatic number
Nathann Cohen, Frédéric Havet, William Lochet, Nicolas Nisse · Journal of Graph Theory · 2018
Abstract 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).