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

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.