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 , Laboratoire I3S - 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00811571
Contributor : Stéphane Bessy <>
Submitted on : Wednesday, April 10, 2013 - 4:28:48 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Thursday, July 11, 2013 - 4:16:20 AM

File

EnumCol.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00811571, version 1

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. ⟨lirmm-00811571⟩

Share

Metrics

Record views

683

Files downloads

411