Change search
ReferencesLink to record
Permanent link

Direct link
Thomassen's Choosability Argument Revisited
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).ORCID iD: 0000-0001-6339-2230
2010 (English)In: SIAM Journal on Discrete Mathematics, ISSN 0895-4801, E-ISSN 1095-7146, Vol. 24, no 4, 1632-1637 p.Article in journal (Refereed) Published
Abstract [en]

Thomassen (J. Combin. Theory Ser. B, 62 (1994), pp. 180-181) proved that every planar graph is 5-choosable. This result was generalized by. Skrekovski (Discrete Math., 190 (1998), pp. 223- 226) and He, Miao, and Shen (Discrete Math., 308 (2008), pp. 4024-4026), who proved that every K-5-minor-free graph is 5-choosable. Both proofs rely on the characterization of K-5-minor-free graphs due to Wagner (Math. Ann., 114 (1937), pp. 570-590). 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.

Place, publisher, year, edition, pages
2010. Vol. 24, no 4, 1632-1637 p.
Keyword [en]
Graph coloring, graph minor, choosability, list coloring, Hadwiger Conjecture
National Category
Engineering and Technology
URN: urn:nbn:se:kth:diva-28904DOI: 10.1137/100796649ISI: 000285505800026ScopusID: 2-s2.0-79251578348OAI: diva2:414087
QC 20110501Available from: 2011-05-02 Created: 2011-01-24 Last updated: 2011-05-02Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Linusson, Svante
By organisation
Mathematics (Div.)
In the same journal
SIAM Journal on Discrete Mathematics
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 23 hits
ReferencesLink to record
Permanent link

Direct link