Thomassen's choosability argument revisited

DOI10.1137/100796649MaRDI QIDQ3013152zbMATH OpenOpenAlexFDO

Authors David R. Wood, Svante Linusson

Publication date 18 July 2011

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

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

zbMATH Keywords

graph coloringlist coloringchoosabilitygraph minorHadwiger conjecture

Mathematics Subject Classification ID

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

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.

Recommendations

• Choosability of K₅-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

Cited in

(7)

• Rooted K₄-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₅-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)