3-facial colouring of plane graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2006

3-facial colouring of plane graphs

Résumé

A plane graph is l-facially k-colourable if its vertices can be coloured with k colours such that any two distinct vertices on a facial segment of length at most l are coloured differently. We prove that every plane graph is 3-facially 11-colourable. As a consequence, we derive that every 2-connected plane graph with maximum face-size at most 7 is cyclically 11-colourable. These two bounds are for one off from those that are proposed by the (3l+1)-Conjecture and the Cyclic Conjecture.
Fichier principal
Vignette du fichier
squelette-rr.pdf (229.38 Ko) Télécharger le fichier

Dates et versions

inria-00083533 , version 1 (02-07-2006)
inria-00083533 , version 2 (04-07-2006)
inria-00083533 , version 3 (07-07-2006)
inria-00083533 , version 4 (30-06-2010)

Identifiants

Citer

Frédéric Havet, Jean-Sébastien Sereni, Riste Skrekovski. 3-facial colouring of plane graphs. [Research Report] RR-5943, 2006, pp.26. ⟨inria-00083533v2⟩

Collections

INRIA-RRRT
212 Consultations
253 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More