Facial parity edge colouring

Abstract : A facial parity edge colouring of a connected bridgeless plane graph is an edge colouring in which no two face-adjacent edges (consecutive edges of a facial walk of some face) receive the same colour, in addition, for each face α and each colour c, either no edge or an odd number of edges incident with α is coloured with c. From Vizing's theorem it follows that every 3-connected plane graph has a such colouring with at most Δ* + 1 colours, where Δ* is the size of the largest face. In this paper we prove that any connected bridgeless plane graph has a facial parity edge colouring with at most 92 colours.
Type de document :
Article dans une revue
Ars Mathematica Contemporanea, DMFA Slovenije, 2011, 4 (2), pp.255-269. <http://amc.imfm.si/index.php/amc/article/view/129>
Liste complète des métadonnées


https://hal.inria.fr/inria-00634947
Contributeur : František Kardoš <>
Soumis le : mercredi 9 novembre 2011 - 13:53:29
Dernière modification le : jeudi 27 mars 2014 - 10:58:56
Document(s) archivé(s) le : vendredi 10 février 2012 - 02:21:16

Fichier

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

Identifiants

  • HAL Id : inria-00634947, version 1

Collections

Citation

Július Czap, Stanislav Jendrol', František Kardoš. Facial parity edge colouring. Ars Mathematica Contemporanea, DMFA Slovenije, 2011, 4 (2), pp.255-269. <http://amc.imfm.si/index.php/amc/article/view/129>. <inria-00634947>

Partager

Métriques

Consultations de
la notice

143

Téléchargements du document

279