Enumerating the edge-colourings and total colourings of a regular graph - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2012

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

Résumé

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.
Fichier principal
Vignette du fichier
EnumCol.pdf (1.35 Mo) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00811571 , version 1 (10-04-2013)

Identifiants

  • HAL Id : lirmm-00811571 , version 1

Citer

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. ⟨lirmm-00811571⟩
411 Consultations
343 Téléchargements

Partager

More