Recent progress towards Hadwiger's conjecture (Q6198638)

This paper is a survey for the 2022 ICM on Hadwiger's conjecture, the famous assertion that every graph with no \(K_{t}\) minor has chromatic number \(\leq t-1\). If true, this would be sharp (consider \(K_{t-1}\)). Very small values of \(t\) can be dealt with directly, but even the case \(t=5\) is known to be equivalent to the (seemingly very hard) four-colour theorem. \textit{N. Robertson} et al. [Combinatorica 13, No. 3, 279--361 (1993; Zbl 0830.05028)] managed to deal with \(t=6\) by a further reduction to the four-colour theorem but cases with \(t\geq 7\) are unresolved at present. The survey concentrates on two weaker forms of the conjecture. The first of these is the obvious weaker form, the so-called linear Hadwiger's conjecture, that there is a constant \(C\geq 1\) such that every graph with no \(K_{t}\)-minor is \(Ct\)-colourable. The second is the so-called \(H\)-Hadwiger's conjecture, due to \textit{P. Seymour} [in: Open problems in mathematics. Cham: Springer. 417--437 (2016; Zbl 1347.05079)], which is the assertion that for every graph \(H\) on \(t\) vertices, every graph with no \(H\)-minor is \((t-1)\) colourable. The survey focuses on tools relying on the interplay of very basic parameters of the graph such as its density (number of edges over number of vertices), its vertex-connectivity, and its chromatic number. An important role in density arguments is played by the function \(c(H)\), defined to be the supremum of the density taken over all non-null graphs not containing \(H\) as a minor, results on which are surveyed. An important technique is the so-called density increment argument, which we introduce here as saying that every graph has to contain either a substantially denser minor or a small subgraph with density not substantially lower than the whole graph -- see Section 4 of the paper for precise statements. This allows the construction of minors by combining pieces from the dense subgraphs; this intuition is made precise in Section 5. Section 6 illustrates how these ideas can be used to prove a result of \textit{S. Norin} and \textit{L. Postle} [J. Comb. Theory, Ser. B 158, Part 1, 283--300 (2023; Zbl 1504.05273)]. This result allows the author to reprove a result of \textit{B. Reed} and \textit{D. R. Wood} [Comb. Probab. Comput. 25, No. 2, 300--322 (2016; Zbl 1372.05211)] that, for every \(\beta>1/4\), graphs with no \(K_{t}\)-minor are \(O(t\log(t)^{\beta})\)-colourable, which improved the long-standing best bound \(O(t\sqrt{\log(t)})\) proved independently by \textit{A. V. Kostochka} [Transl., Ser. 2, Am. Math. Soc. 132, 15--31 (1986; Zbl 0595.05041); Combinatorica 4, 307--316 (1984; Zbl 0555.05030)] and by \textit{A. Thomason} [J. Comb. Theory, Ser. B 81, No. 2, 318--338 (2001; Zbl 1024.05083)] (a short proof of this order of magnitude, with suboptimal constants, was given by \textit{M. Krivelevich} and \textit{B. Sudakov} [Geom. Funct. Anal. 19, No. 1, 294--331 (2009; Zbl 1227.05230)]). The current state of the art, using amongst other things a number of the ideas in this survey, is the bound \(O(t\log\log(t))\) from [\textit{M. Delcourt} and \textit{L. Postle}, ``Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs'', Preprint, arXiv:2108.01633 [math.CO] (2021)]. For the entire collection see [Zbl 07816360].