Hadwiger's conjecture is decidable

DOI10.1145/1536414.1536476MaRDI QIDQ5172739zbMATH OpenOpenAlexFDO

Authors Ken-ichi Kawarabayashi, Bruce Reed

Publication date 4 February 2015

Published in Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1536414.1536476

zbMATH Keywords

four-color theoremHadwiger's conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Hadwiger's conjecture for \(K_ 6\)-free graphs
• scientific article; zbMATH DE number 54802
• Coloring graphs with forbidden minors
• Local Hadwiger's conjecture
• Matchings and Hadwiger's conjecture

Cited in

(13)

• Fast minor testing in planar graphs
• Additive non-approximability of chromatic number in proper minor-closed classes
• Subdivisions of \(K_{5}\) in graphs embedded on surfaces with face-width at least 5
• Graph minors and parameterized algorithm design
• The Join Levels of the Trotter-Weil Hierarchy Are Decidable
• scientific article; zbMATH DE number 5999552 (Why is no real title available?)
• List-coloring graphs without subdivisions and without immersions
• Combing a Linkage in an Annulus
• scientific article; zbMATH DE number 7724207 (Why is no real title available?)
• Faster parameterized algorithms for minor containment
• Computing paths of large rank in planar frameworks deterministically
• Computing paths of large rank in planar frameworks deterministically
• Finite dualities and map-critical graphs on a fixed surface

This page was built for publication: Hadwiger's conjecture is decidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5172739)