We investigate bounds on the dichromatic number of digraphs which avoid a fixed digraph as a topological minor. For a digraph F, denote by mader ((x)over-right-arrow)(F) the smallest integer k such that every k-dichromatic digraph contains a subdivision of F. As our first main result, we prove that if F is an orientation of a cycle then mader, ((x)over-right-arrow)(F) = v(F). This settles a conjecture of Aboulker, Cohen, Havet, Lochet, Moura and Thomasse. We also extend this result to the more general class of orientations of cactus graphs, and to bioriented forests. Our second main result is that mader (x)over-right-arrow (F) = 4 for every tournament F of order 4. This is an extension of the classical result by Dirac that 4-chromatic graphs contain a K-4-subdivision to directed graphs. (C) 2021 Elsevier Inc. All rights reserved.
NSTL
Elsevier
