Recent progress towards Hadwiger's conjecture
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].
- A local epsilon version of Reed's conjecture
- A lower bound on the average degree forcing a minor
- A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
- A Separator Theorem for Nonplanar Graphs
- An extremal function for contractions of graphs
- An improved linear edge bound for graph linkages
- Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
- Complete minors in \(K_{s,s}\)-free graphs
- Contractions to k8
- Dense graphs have \(K_{3,t}\) minors
- Densities of minor-closed graph families
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
- Extremal density for sparse minors and subdivisions
- Extremal functions for rooted minors
- Forcing unbalanced complete bipartite minors
- Fractional colouring and Hadwiger's conjecture
- Hadwiger's conjecture
- Hadwiger's conjecture for \(K_ 6\)-free graphs
- Highly linked graphs
- Homomorphieeigenschaften und mittlere Kantendichte von Graphen
- Homomorphiesätze für Graphen
- Homomorphism theorems for graphs
- scientific article; zbMATH DE number 2127501 (Why is no real title available?)
- scientific article; zbMATH DE number 3865318 (Why is no real title available?)
- scientific article; zbMATH DE number 3102312 (Why is no real title available?)
- Lower bound of the Hadwiger number of graphs by their average degree
- Minors in expanding graphs
- Minors in graphs of large girth
- On \(K_{s,t}\)-minors in graphs with given average degree
- On Hadwiger's Number and the Stability Number
- On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture
- Proof of the bandwidth conjecture of Bollobás and Komlós
- Some recent progress and applications in graph minor theory
- Strongly sublinear separators and polynomial expansion
- Subcontraction-equivalence and Hadwiger's conjecture
- The edge-density for \(K_{2,t}\) minors
- The extremal function for \(K_{9}\) minors
- The extremal function for complete minors
- The extremal function for disconnected minors
- The extremal function for noncomplete minors
- The extremal function for Petersen minors
- The extremal function for unbalanced bipartite minors
- The history of degenerate (bipartite) extremal graph problems
- Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs
- On a recolouring version of Hadwiger's conjecture
- Hadwiger's conjecture and topological bounds
- Odd clique minors and chromatic bounds of {\(3K_1\), paraglider}-free graphs
- Odd complete bipartite minors in graphs with independence number two
This page was built for publication: Recent progress towards Hadwiger's conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6198638)
