Raphael Steiner, Strengthening Hadwiger’s conjecture for 4- and 5-chromatic graphs

Hadwiger’s famous coloring conjecture states that every t-chromatic graph contains a $K_t$-minor. Holroyd [Bull. London Math. Soc. 29, (1997), pp. 139-144] conjectured the following strengthening of Hadwiger’s conjecture: If G is a t-chromatic graph and S⊆V(G) takes all colors in every t-coloring of G, then G contains a $K_t$-minor rooted at S. We prove this conjecture in the first open case of t=4. Notably, our result also directly implies a stronger version of Hadwiger’s conjecture for 5-chromatic graphs as follows: Every 5-chromatic graph contains a $K_5$-minor with a singleton branch-set. In fact, in a 5-vertex-critical graph we may specify the singleton branch-set to be any vertex of the graph. Joint work with Anders Martinsson (ETH).

Raphael Steiner gave an online talk on finding a subdivision of a fixed directed graph with conditions on the length of a path replacing each edge in a digraph of large dichromatic number at the Virtual Discrete Math Colloquium

On August 31, 2022, Raphael Steiner from the ETH Zürich gave an online at the Virtual Discrete Math Colloquium on the existence of a subdivision of a fixed digraph satisfying constraints on the length of a path replacing each edge in a directed graph of large dichromatic number. The title of his talk was “Congruence-constrained subdivisions in digraphs“.

Raphael Steiner, Congruence-constrained subdivisions in digraphs

I will present the short proof from [1] that for every digraph F and every assignment of pairs of integers $(r_e,q_e)_{e\in A(F)}$ to its arcs, there exists an integer $N$ such that every digraph D with dichromatic number at least $N$ contains a subdivision of $F$ in which $e$ is subdivided into a directed path of length congruent to $r_e$ modulo $q_e$ for every $e \in A(F)$. This generalizes to the directed setting the analogous result by Thomassen for undirected graphs and at the same time yields a novel proof of his result. I will also talk about how a hypergraph coloring result from [2] may help to obtain good bounds on $N$ in the special case when $F$ is subcubic.

기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209