Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Thursday, February 25, 2021, 12:15 pm

Duration: 30 minutes

Location: Zoom: conference room

Speaker: Raphael Steiner (TU Berlin)

Subdivisions, minors and colorings of digraphs

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ó.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login