5-colouring graphs with 4 crossings

Rok Erman (1) , Frédéric Havet (2) , Bernard Lidicky (3) , Ondrej Pangrac (3)

1 Departement of Mathematics [Slovenia]
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
3 ITI - Institute for Theoretical Computer Science

We disprove a conjecture of Oporowski and Zhao stating that every graph with crossing number at most 5 and clique number at most 5 is 5-colourable. However, we show that every graph with crossing number at most 4 and clique number at most 5 is 5-colourable. We also show some colourability results on graphs that can be made planar by removing few edges. In particular, we show that if there exists three edges whose removal leaves the graph planar then it is 5-colourable.

Domaines: Mathématique discrète [cs.DM]

Rok Erman, Frédéric Havet, Bernard Lidicky, Ondrej Pangrac. 5-colouring graphs with 4 crossings. [Research Report] RR-7110, INRIA. 2009. ⟨inria-00437726⟩