Enumerating the edge-colourings and total colourings of a regular graph

Stéphane Bessy 1 Frédéric Havet 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Motivated by some algorithmic considerations, we are interested in computing the number of edge colourings of a connected graph. Precisely, we prove that the maximum number of k-edge-colourings of a connected k-regular graph on n vertices is k((k-1)!)^{n/2}. Our proof is constructive and leads to a branching algorithm enumerating all the k-edge-colourings of a connected k-regular graph in time O*(((k-1)!)^{n/2}) and polynomial space. In particular, we obtain a algorithm to enumerate all the 3-edge-colourings of a connected cubic graph in time O*(2^{n/2})=O*(1.4143^n) and polynomial space. This improves the running time of O*(1.5423^n) of the algorithm due to Golovach, Kratsh and Couturier [WG10]. In this talk, I will present our work and overview the known results on computing aspect of graph coloring.
Type de document :
Communication dans un congrès
2012 Workshop on Graph Theory and Combinatorics, Aug 2012, National Sun Yat-sen University, Kaohsiung, Taiwan. 2012, <http://www.math.nsysu.edu.tw/~comb/2012/>
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00811571
Contributeur : Stéphane Bessy <>
Soumis le : mercredi 10 avril 2013 - 16:28:48
Dernière modification le : mercredi 20 janvier 2016 - 14:28:29
Document(s) archivé(s) le : jeudi 11 juillet 2013 - 04:16:20

Fichier

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

Identifiants

  • HAL Id : lirmm-00811571, version 1

Collections

Citation

Stéphane Bessy, Frédéric Havet. Enumerating the edge-colourings and total colourings of a regular graph. 2012 Workshop on Graph Theory and Combinatorics, Aug 2012, National Sun Yat-sen University, Kaohsiung, Taiwan. 2012, <http://www.math.nsysu.edu.tw/~comb/2012/>. <lirmm-00811571>

Partager

Métriques

Consultations de
la notice

244

Téléchargements du document

186