Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Identifiers
URN: urn:nbn:se:kth:diva-28904DOI: 10.1137/100796649ISI: 000285505800026Scopus ID: 2-s2.0-79251578348OAI: oai:DiVA.org:kth-28904DiVA: diva2:414087
Note
QC 20110501Available from: 2011-05-02 Created: 2011-01-24 Last updated: 2017-12-11Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Linusson, Svante

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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 40 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf