Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [6 references]  Display  Hide  Download
Contributor : Stéphane Bessy Connect in order to contact the contributor
Submitted on : Wednesday, April 10, 2013 - 4:28:48 PM
Last modification on : Friday, October 22, 2021 - 3:07:27 PM
Long-term archiving on: : Thursday, July 11, 2013 - 4:16:20 AM


Files produced by the author(s)


  • HAL Id : lirmm-00811571, version 1


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⟩



Record views


Files downloads