Skip to Main content Skip to Navigation
Reports

5-colouring graphs with 4 crossings

Rok Erman 1 Frédéric Havet 2 Bernard Lidicky 3 Ondrej Pangrac 3
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Document type :
Reports
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00437726
Contributor : Frederic Havet <>
Submitted on : Tuesday, December 1, 2009 - 12:13:08 PM
Last modification on : Monday, December 14, 2020 - 3:30:28 PM
Long-term archiving on: : Tuesday, October 16, 2012 - 3:10:34 PM

File

RR-7110.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00437726, version 1

Citation

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

Share

Metrics

Record views

376

Files downloads

230