3-facial colouring of plane graphs

Frédéric Havet 1 Jean-Sébastien Sereni 1 Riste Skrekovski 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : 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.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2008, 22 (1), pp.231--247. <10.1137/060664124>
Liste complète des métadonnées

https://hal.inria.fr/inria-00083533
Contributeur : Jean-Sébastien Sereni <>
Soumis le : mercredi 30 juin 2010 - 17:43:30
Dernière modification le : jeudi 1 juillet 2010 - 08:43:51
Document(s) archivé(s) le : lundi 4 octobre 2010 - 13:07:34

Fichier

HSS08.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Frédéric Havet, Jean-Sébastien Sereni, Riste Skrekovski. 3-facial colouring of plane graphs. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2008, 22 (1), pp.231--247. <10.1137/060664124>. <inria-00083533v4>

Partager

Métriques

Consultations de
la notice

284

Téléchargements du document

105