5-colouring graphs with 4 crossings - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Discrete Mathematics Année : 2011

5-colouring graphs with 4 crossings

Résumé

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.
Fichier principal
Vignette du fichier
colcross-final.pdf (401.95 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00638434 , version 1 (23-10-2016)

Identifiants

Citer

Rok Erman, Frédéric Havet, Bernard Lidický, Ondrej Pangrac. 5-colouring graphs with 4 crossings. SIAM Journal on Discrete Mathematics, 2011, 25 (1), pp.401-422. ⟨10.1137/100784059⟩. ⟨inria-00638434⟩
158 Consultations
86 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More