Breaking the degeneracy barrier for coloring graphs with no \(K_t\) minor

DOI10.1016/j.aim.2023.109020OpenAlexW4365520282MaRDI QIDQ2700634

Luke Postle, Serguei Norine, Zi-Xia Song

Publication date: 27 April 2023

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1910.09378

zbMATH Keywords

graph coloringHadwiger's conjecturegraph minors

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph minors (05C83)

Related Items (6)

Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs ⋮ Local Hadwiger's conjecture ⋮ Refined List Version of Hadwiger’s Conjecture ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ Immersion and clustered coloring ⋮ Connectivity and choosability of graphs with no \(K_t\) minor

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complete minors in \(K_{s,s}\)-free graphs
• Disproof of the list Hadwiger conjecture
• List colourings of planar graphs
• 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
• A relaxed Hadwiger's conjecture for list colorings
• Minors in expanding graphs
• On the maximum density of graphs which have no subcontraction to \(K^ r\).
• 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 four-colour theorem
• Fractional colouring and Hadwiger's conjecture
• An improved linear edge bound for graph linkages
• Cycles of even length in graphs
• The extremal function for complete minors
• Connectivity and choosability of graphs with no \(K_t\) minor
• Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
• Highly linked graphs
• Über eine Eigenschaft der ebenen Komplexe
• Hadwiger’s Conjecture
• An extremal function for contractions of graphs
• On Hadwiger's Number and the Stability Number
• Subcontraction-equivalence and Hadwiger's conjecture
• Minors in graphs of large girth
• The History of Degenerate (Bipartite) Extremal Graph Problems
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• On a problem of K. Zarankiewicz
• Improved lower bound for the list chromatic number of graphs with no K_t minor
• A local epsilon version of Reed's conjecture

This page was built for publication: Breaking the degeneracy barrier for coloring graphs with no \(K_t\) minor