Complete directed minors and chromatic number

Abstract

The dichromatic number $\overrightarrow{\chi }(D)$ of a digraph $D$ is the smallest $k$ for which it admits a $k$-coloring where every color class induces an acyclic subgraph. Inspired by Hadwiger's conjecture for undirected graphs, several groups of authors have recently studied the containment of complete directed minors in digraphs with a given dichromatic number. In this note we exhibit a relation of these problems to Hadwiger's conjecture. Exploiting this relation, we show that every directed graph excluding the complete digraph ${\overleftrightarrow{K}}_{t}$ of order $t$ as a strong minor or as a butterfly minor is $O(t{(\mathrm{log}\unicode{x0200A}\mathrm{log}\unicode{x0200A}t)}^{6})$-colorable. This answers a question by Axenovich, Girao, Snyder, and Weber, who proved an upper bound of $t{4}<^>{t}$ for the same problem. A further consequence of our results is that every digraph of dichromatic number $22n$ contains a subdivision of every $n$-vertex subcubic digraph, which makes progress on a set of problems raised by Aboulker, Cohen, Havet, Lochet, Moura, and Thomasse.