Enumerating the edge-colourings and total colourings of a regular graph - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2012

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

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.
Fichier principal
Vignette du fichier
EnumCol.pdf (1.35 Mo) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

  • HAL Id : lirmm-00811571 , version 1

Cite

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⟩
404 View
326 Download

Share

More