Skip to main content
profile image
Selected Works of Bernard Lidický
Article
Graphs with Two Crossings Are 5-Choosable
SIAM Journal on Discrete Mathematics (2011)
  • Zdeněk Dvořák, Charles University, Prague
  • Bernard Lidicky, Charles University, Prague
  • Riste Škrekovski, University of Ljubljana
Download Find in your library
Abstract
A graph G is k-choosable if G can be properly colored whenever every vertex has a
list of at least k available colors. Thomassen’s theorem states that every planar graph is 5-choosable.
We extend the result by showing that every graph with at most two crossings is 5-choosable.
Keywords
  • choosability,
  • graph coloring,
  • crossing number
Disciplines
Publication Date
2011
DOI
10.1137/11082703X
Publisher Statement
Copyright 2011 Society for Industrial and Applied Mathematics
Citation Information
Zdeněk Dvořák, Bernard Lidicky and Riste Škrekovski. "Graphs with Two Crossings Are 5-Choosable" SIAM Journal on Discrete Mathematics Vol. 25 Iss. 4 (2011) p. 1746 - 1753
Available at: http://works.bepress.com/bernard-lidicky/6/
Creative Commons license
Creative Commons License
This work is licensed under a Creative Commons CC_BY-NC International License.