List colouring squares of planar graphs

Abstract : In 1977, Wegner conjectured that the chromatic number of the square of every planar graph~$G$ with maximum degree $\Delta\ge8$ is at most $\bigl\lfloor\frac32\,\Delta\bigr\rfloor+1$. We show that it is at most $\frac32\,\Delta\,(1+o(1))$, and indeed this is true for the list chromatic number and for more general classes of graphs.
Type de document :
Rapport
[Research Report] RR-6586, INRIA. 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00303303
Contributeur : Frederic Havet <>
Soumis le : lundi 21 juillet 2008 - 21:57:58
Dernière modification le : jeudi 11 janvier 2018 - 16:50:43
Document(s) archivé(s) le : jeudi 4 octobre 2012 - 14:48:29

Fichier

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

Identifiants

  • HAL Id : inria-00303303, version 1

Citation

Frédéric Havet, Jan Van den Heuvel, Colin Mcdiarmid, Bruce Reed. List colouring squares of planar graphs. [Research Report] RR-6586, INRIA. 2008. 〈inria-00303303〉

Partager

Métriques

Consultations de la notice

311

Téléchargements de fichiers

166