Thomassen's choosability argument revisited

DOI10.1137/100796649zbMATH Open1221.05290arXiv1005.5194OpenAlexW2080290857MaRDI QIDQ3013152FDOQ3013152

Authors: David R. Wood, Svante Linusson 

Publication date: 18 July 2011

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Thomassen (1994) proved that every planar graph is 5-choosable. This result was generalised by {v{S}}krekovski (1998) and He et al. (2008), who proved that every $K_5$-minor-free graph is 5-choosable. Both proofs rely on the characterisation of $K_5$-minor-free graphs due to Wagner (1937). This paper proves the same result without using Wagner's structure theorem or even planar embeddings. Given that there is no structure theorem for graphs with no $K_6$-minor, we argue that this proof suggests a possible approach for attacking the Hadwiger Conjecture.

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

Recommendations

• Choosability of \(K_5\)-minor-free graphs
• Disproof of the list Hadwiger conjecture
• Another proof of the 5-choosability of \(K_5\)-minor-free graphs
• An extension of Thomassen's result on choosability
• Graphs with two crossings are 5-choosable

zbMATH Keywords

graph coloringlist coloringchoosabilitygraph minorHadwiger conjecture

Mathematics Subject Classification ID

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

Cited In (7)

• Rooted \(K_4\)-minors
• An extension of Thomassen's result on choosability
• Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs
• Another proof of the 5-choosability of \(K_5\)-minor-free graphs
• Choosability of \(K_5\)-minor-free graphs
• The extremal function for Petersen minors
• The Alon-Tarsi number of \(K_5\)-minor-free graphs

This page was built for publication: Thomassen's choosability argument revisited

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