REVIEW
Dichromatic number and forced subdivisions
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Dichromatic number and forced subdivisions
read the original 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 $\text{mader}_{\vec{\chi}}(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 $\text{mader}_{\vec{\chi}}(F)=v(F)$. This settles a conjecture of Aboulker, Cohen, Havet, Lochet, Moura and Thomass\'{e}. 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 $\text{mader}_{\vec{\chi}}(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.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.