5-Coloring Graphs with 4 Crossings
Rok Erman, Frédéric Havet, Bernard Lidický, Ondřej Pangrác · SIAM Journal on Discrete Mathematics · 2011
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.