Recent progress towards Hadwiger's conjecture

DOI10.4171/icm2022/102MaRDI QIDQ6198638

Serguei Norine

Publication date: 20 March 2024

Published in: International Congress of Mathematicians (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4171/icm2022/102

zbMATH Keywords

graph coloring; extremal function; Hadwiger's conjecture; graph minors; density increment

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C83: Graph minors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complete minors in \(K_{s,s}\)-free graphs
• Densities of minor-closed graph families
• The edge-density for \(K_{2,t}\) minors
• Forcing unbalanced complete bipartite minors
• Dense graphs have \(K_{3,t}\) minors
• Lower bound of the Hadwiger number of graphs by their average degree
• On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture
• Some recent progress and applications in graph minor theory
• On \(K_{s,t}\)-minors in graphs with given average degree
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Minors in expanding graphs
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• The extremal function for unbalanced bipartite minors
• Fractional colouring and Hadwiger's conjecture
• The extremal function for Petersen minors
• An improved linear edge bound for graph linkages
• The extremal function for complete minors
• A lower bound on the average degree forcing a minor
• The extremal function for noncomplete minors
• The extremal function for disconnected minors
• The extremal function for \(K_{9}\) minors
• Homomorphiesätze für Graphen
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
• Highly linked graphs
• Homomorphism theorems for graphs
• Strongly Sublinear Separators and Polynomial Expansion
• Hadwiger’s Conjecture
• An extremal function for contractions of graphs
• Extremal functions for rooted minors
• On Hadwiger's Number and the Stability Number
• Subcontraction-equivalence and Hadwiger's conjecture
• A Separator Theorem for Nonplanar Graphs
• Contractions to k₈
• Minors in graphs of large girth
• Extremal density for sparse minors and subdivisions
• The History of Degenerate (Bipartite) Extremal Graph Problems
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• A local epsilon version of Reed's conjecture