Mader-perfect digraphs

Abstract: We investigate the relationship of dichromatic number and subdivision containment in digraphs. We call a digraph Mader-perfect if for every (induced) subdigraph $F$, any digraph of dichromatic number at least $v(F)$ contains an $F$-subdivision. We show that, among others, arbitrary orientated cycles, bioriented trees, and tournaments on four vertices are Mader-perfect. The first result settles a conjecture of Aboulker, Cohen, Havet, Lochet, Moura, and Thomasse, while the last one extends Dirac's Theorem about $4$-chromatic graphs containing a $K_4$-subdivision to directed graphs. The talk represents joint work with Lior Gishboliner and Raphael Steiner.

combinatorics

Audience: researchers in the topic

Warwick Combinatorics Seminar

Series comments: This is the online combinatorics seminar at Warwick.