Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs
Anders Martinsson, Raphael Steiner · Journal of Combinatorial Theory Series B · 2023
Four-Color-Theorem Rooted minorsHadwiger's famous coloring conjecture states that every tchromatic graph contains a K t -minor.Holroyd [11] 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.