Combinatorics Seminar


Speaker: Raphael Steiner

Title: Complete minors via dichromatic number

Abstract: The dichromatic number of a directed graph is the smallest integer k for which the vertex-set of the graph can be partitioned into k acyclic sets (not spanning a directed cycle).

Inspired by the famous Hadwiger conjecture for undirected graphs, several groups of authors have recently studied the containment of complete digraph minors in directed graphs with given dichromatic number. We present a very short argument which improves the existing exponential upper bounds to almost linear bounds by reducing the problem to a recent result of Postle on Hadwiger's conjecture.

The talk represents recent joint work with Tamás Mészáros (FU Berlin).