5-colouring graphs with 4 crossings

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.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2011, 25 (1), pp.401-422. 〈10.1137/100784059〉
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-00638434
Contributeur : Frederic Havet <>
Soumis le : dimanche 23 octobre 2016 - 16:20:01
Dernière modification le : lundi 4 décembre 2017 - 15:14:09

Fichier

colcross-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Rok Erman, Frédéric Havet, Bernard Lidický, Ondrej Pangrac. 5-colouring graphs with 4 crossings. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2011, 25 (1), pp.401-422. 〈10.1137/100784059〉. 〈inria-00638434〉

Partager

Métriques

Consultations de la notice

187

Téléchargements de fichiers

93