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

1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In this paper, we are interested in computing the number of edge colourings and total colourings of a graph. We prove that the maximum number of $k$-edge-colourings of a $k$-regular graph on $n$ vertices is $k\cdot(k-1!)^{n/2}$. Our proof is constructible and leads to a branching algorithm enumerating all the $k$-edge-colourings of a $k$-regular graph using a time $O^*((k-1!)^{n/2})$ and polynomial space. In particular, we obtain a algorithm on time $O^*(2^{n/2})=O^*(1.4143^n)$ and polynomial space to enumerate all the $3$-edge colourings of a cubic graph, improving the running time of $O^*(1.5423^n)$ of the algorithm due to Golovach et al.~\cite{GKC10}. We also show that the number of $4$-total-colourings of a connected cubic graph is at most $3.2^{3n/2}$. Again, our proof yields a branching algorithm to enumerate all the $4$-total-colourings of a connected cubic graph.
Type de document :
Rapport
[Research Report] RR-7652, INRIA. 2011
Liste complète des métadonnées

Littérature citée [16 références]

https://hal.inria.fr/inria-00602188
Contributeur : Frederic Havet <>
Soumis le : mardi 21 juin 2011 - 17:00:40
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : vendredi 9 novembre 2012 - 16:46:24

### Fichier

RR-7652.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : inria-00602188, version 1

### Citation

Stéphane Bessy, Frédéric Havet. Enumerating the edge-colourings and total colourings of a regular graph. [Research Report] RR-7652, INRIA. 2011. 〈inria-00602188〉

### Métriques

Consultations de la notice

## 384

Téléchargements de fichiers