Thomassen's Choosability Argument Revisited

Details Thomassen's Choosability Argument Revisited Thomassen's Choosability Argument Revisited

2010-05-27

arxiv.org/abs/1005.5194v3

SIAM J. Discrete Mathematics 24(4):1632-1637, 2010

Mathematics

Combinatorics

Scientific paper

10.1137/100796649

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.

Affiliated with

Also associated with

No associations

Rating

Thomassen's Choosability Argument Revisited does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Thomassen's Choosability Argument Revisited, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Thomassen's Choosability Argument Revisited will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-15499