Skip to main content
profile image
Selected Works of Bernard Lidický
Article
5-Coloring Graphs with 4 Crossings
SIAM Journal on Discrete Mathematics (2011)
  • Rok Erman, University of Ljubljana
  • Bernard Lidicky, Charles University, Prague
  • Frédéric Havet, I3S
  • Ondřej Pangrác, Charles University, Prague
Download Find in your library
Abstract
We answer in the negative a question of Oporowski and Zhao [Discrete Math., 309
(2009), pp. 2948–2951] asking whether every graph with crossing number at most 5 and clique number
at most 5 is 5-colorable. However, we show that every graph with crossing number at most 4 and
clique number at most 5 is 5-colorable. We also show some colorability results on graphs that can be
made planar by removing a few edges. In particular, we show that, if a graph with clique number at
most 5 has three edges whose removal leaves the graph planar, then it is 5-colorable.
Keywords
  • chromatic number,
  • crossing number,
  • clique number,
  • girth
Disciplines
Publication Date
2011
DOI
10.1137/100784059
Publisher Statement
Copyright 2011 Society for Industrial and Applied Mathematics
Citation Information
Rok Erman, Bernard Lidicky, Frédéric Havet and Ondřej Pangrác. "5-Coloring Graphs with 4 Crossings" SIAM Journal on Discrete Mathematics Vol. 25 Iss. 1 (2011) p. 401 - 422
Available at: http://works.bepress.com/bernard-lidicky/5/
Creative Commons license
Creative Commons License
This work is licensed under a Creative Commons CC_BY-NC International License.