Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, February 25, 2021, 12:15 pm
Duration: 30 minutes
Location: Zoom: conference room
Speaker: Raphael Steiner (TU Berlin)
Driven by Hadwiger's conjecture and its relatives, conditions enforcing the existence of a subdivision or a minor of a fixed graph in graphs with large chromatic number or large average/minimum degree is a classical research subject in graph theory, and many asymptotically tight results have been proved in the past: Quadratic average degree forces subdivisions of complete graphs, and slightly superlinear average degree forces complete minors. This situation changes dramatically when considering natural generalizations of subdivisions and minors to digraphs. For one, it follows from known constructions in the literature that not even the complete digraph on 3 vertices can be forced as a subdivision or as a minor by means of large minimum (out- and in-) degrees. A conjecture by Mader from 1985 claims that digraphs of sufficiently large minimum outdegree contain subdivisions of any acyclic digraph, but also this remains widely open. An established extension of the chromatic number to directed graphs is the dichromatic number introduced in 1980 by Erdős and Neumann-Lara, which seeks the smallest partition of the vertex-set of a digraph into acyclic subsets. Aboulker et al. (2016) and Axenovich et al. (2020) proved that in contrast to minimum degrees, large dichromatic number is capable of forcing complete digraph subdivisions/minors. Axenovich et al. showed an upper bound on the dichromatic number of digraphs excluding a fixed complete digraph as a minor. However, their bound is exponential, and they raised the problem of improving it. In this talk I will present an almost linear upper bound for this problem by reducing the problem to recent progress on Hadwiger's conjecture, and give a quick survey of related results. The talk is based on joint work with Tamás Mészáros and with Lior Gishboliner and Tibor Szabó.
Automatic MiSe System Software Version 1.4803M | admin login