Reducing linear Hadwiger's conjecture to coloring small graphs (Q7017022)

A graph \(G\) has an \(H\) minor if a graph isomorphic to a graph \(H\) can be obtained from a subgraph of \(G\) by contracting edges. The linear Hadwiger conjecture states that there exists a constant \(C>0\) such that for every integer \(t\ge1\), every graph with no \(K_t\) minor is \(C\cdot t\)-colorable. The main result of the present paper is \N\NTheorem 1.6: For any graph \(G\) with no \(K_t\) minor, and any integer \(t\ge3\), there exists an integer \(C=C_{1.6}\ge1\) such that, if \(f_{1.6}(G,t)\) denotes \N\[\N\max\limits_{H\subseteq G}\left\{\frac{\chi(H)}a:t\ge a\ge\frac{t}{\sqrt{\ln t}},V(H)\le C\cdot a\cdot (\ln a)^4,H\text{ is }K_a\text{-minor-free}\right\}, \N\]\Nthen \(\chi(G)\le C\cdot t\cdot(1+f_{1.6}(G,t))\).\N\NAs one corollary, the authors prove \N\NTheorem 1.5: Every graph with no \(K_t\) minor is \(\operatorname{O}(t\ln\ln t)\)-colorable, which improves on Theorem 1.4 of [\textit{S. Norin} et al., Adv. Math. 422, Article ID 109020, 23 p. (2023; Zbl 1512.05144)], which stated that for every \(\beta>\frac14\), every graph with no \(K_t\) minor is \(\operatorname{O}(t\cdot(\ln t)^\beta)\)-colorable. Other consequences of Theorem 1.6 are \N\NCorollary 1.7: There exists an integer \(C=C_{1.7}\ge1\) such that the following holds: If for every integer \(t\ge3\) we have that every \(K_t\)-minor-free graph \(H\) with at most \(C\cdot t\cdot(\ln t)^4\) vertices satisfies \(\chi(H)\le Ct\), then for every integer \(t\ge3\) we have that every \(K_t\)-minor-free graph \(G\) satisfies \(\chi(G)\le C^2t\).\N\NCorollary 1.8: There exists \(C=C_{1.8}\ge1\) such that the following holds: Let \(t\ge3\) be an integer. If \(G\) is a \(K_t\)-minor-free graph in which the largest complete subgraph has no more than \(\frac{\sqrt{\ln t}}{( \ln\ln t)^2}\) vertices, then \(\chi(G)\le Ct\).\N\NCorollary 1.9: There exists \(C=C_{1.9}\ge1\) such that for every integer \(r\ge3\), there exists \(t_r>0\) such that for all integers \(t\ge t_r\), every \(K_r\)-free \(K_t\)-minor-free graph is \(C_t\)-colorable.\N\NCorollary 1.10: For every integer \(r\ge3\), there exists \(C_r\ge1\) such that for all integers \(t\ge1\), every \(K_r\)-free \(K_t\)-minor-free graph is \(C_r\cdot t\)-colorable.\N\NThe authors also prove \N\NTheorem 2.3: There exists an integer \(C=C_{2.3}\ge1\) such that the following holds: Let \(t\ge1\) be a fixed integer. For every integer \(k\ge t\), if \(G=(V,E)\) is a nonempty graph with density \(\frac{|E|}{|V|}\ge C\cdot k\) and \(G\) contains no \(K_t\) minor, then \(G\) contains a non-empty \(k\)-connected subgraph \(H\) with at most \(C^2\cdot t\cdot(\ln t)^3\) vertices.