Dichromatic number and forced subdivisions
METADATA ONLY
Loading...
Author / Creator
Date
2022-03
Publication Type
Journal Article
ETH Bibliography
no
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
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χ→(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χ→(F)=v(F). This settles a conjecture of Aboulker, Cohen, Havet, Lochet, Moura and Thomassé. 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χ→(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 K4-subdivision to directed graphs.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Journal of Combinatorial Theory, Series B
Volume
153
Pages / Article No.
1 - 30
Publisher
Academic Press
Event
Edition / version
Methods
Geographic location
Date collected
Date created
Subject
Subdivision; Digraph; Dichromatic number; Topological minor
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
02500 - Forschungsinstitut für Mathematik / Institute for Mathematical Research
03672 - Steger, Angelika (emeritus) / Steger, Angelika (emeritus)