기초과학연구원 이산수학그룹
On February 14, 2023, Raphael Steiner from ETH Zürich gave a talk at the Discrete Math Seminar on a stronger version of Hadwiger’s conjecture, which finds a clique minor in which one of its branch set is a singleton. The title of his talk was “Strengthening Hadwiger’s conjecture for 4- and 5-chromatic graphs“. He is currently visiting the IBS discrete mathematics group for 2 weeks.
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).
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“.
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.