Complete directed minors and chromatic number
OPEN ACCESS
Loading...
Author / Producer
Date
2022
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
101 (4)
Pages / Article No.
623 - 632
Publisher
Wiley
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
chromatic number; directed graphs; graph minors; Hadwiger's conjecture
Organisational unit
03672 - Steger, Angelika / Steger, Angelika