5-colouring graphs with 4 crossings

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.
Type de document :
Rapport
[Research Report] RR-7110, INRIA. 2009
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00437726
Contributeur : Frederic Havet <>
Soumis le : mardi 1 décembre 2009 - 12:13:08
Dernière modification le : jeudi 11 janvier 2018 - 15:59:53
Document(s) archivé(s) le : mardi 16 octobre 2012 - 15:10:34

Fichier

RR-7110.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

192

Téléchargements de fichiers

142