TAU Combinatorics Seminar 2020/21

When: Sunday, January 10, 10am
Speaker: Tibor Szabó, Freie Universität Berlin
Title: Forcing subdivisions in 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 every tournament on four vertices is Mader-perfect. This extends to digraphs Dirac's Theorem about $4$-chromatic graphs containing a $K_4$-subdivision. Furthermore we show that arbitrary orientated cycles and bioriented trees are Mader-perfect, which settles a conjecture of Aboulker, Cohen, Havet, Lochet, Moura, and Thomassé.

The talk represents joint work with Lior Gishboliner and Raphael Steiner.