Steinberg's Conjecture and near-colorings

Abstract : Let F be the family of planar graphs without cycles of length 4 and 5. Steinberg's Conjecture (1976) that says every graph of F is 3-colorable remains widely open. Focusing on a relaxation proposed by Erd˝os (1991), many studies proved the conjecture for some subfamilies of F. For example, Borodin et al. proved that every planar graph without cycles of length 4 to 7 is 3- colorable. In this note we propose to relax the problem not on the family of graphs but on the coloring by considering near-colorings. A graph G = (V,E) is said to be (i, j, k)-colorable if its vertex set can be partitioned into three sets V1, V2, V3 such that the graphs G[V1],G[V2],G[V3] induced by the sets V1, V2, V3 have maximum degree at most i, j, k respectively. Under this terminology, Steinberg's Conjecture says that every graph of F is (0, 0, 0)-colorable. A result of Xu (2008) implies that every graph of F is (1, 1, 1)-colorable. Here we prove that every graph of F is (2, 1, 0)-colorable and (4, 0, 0)-colorable.
Type de document :
Rapport
[Research Report] RR-7669, INRIA. 2011
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00605810
Contributeur : Frederic Havet <>
Soumis le : lundi 4 juillet 2011 - 14:09:12
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : mercredi 5 octobre 2011 - 02:23:08

Fichier

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

Identifiants

  • HAL Id : inria-00605810, version 1

Citation

Gerard Chang, Frédéric Havet, Mickael Montassier, André Raspaud. Steinberg's Conjecture and near-colorings. [Research Report] RR-7669, INRIA. 2011. 〈inria-00605810〉

Partager

Métriques

Consultations de la notice

528

Téléchargements de fichiers

243