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
COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In this paper, we are interested in computing the number of edge colourings and total colourings of a connected graph. We prove that the maximum number of $k$-edge-colourings of a connected $k$-regular graph on $n$ vertices is $k\cdot((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 et al.~\cite{GKC10}. We also show that the number of $4$-total-colourings of a connected cubic graph is at most $3\cdot 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 :
Article dans une revue
Journal of Combinatorial Optimization, Springer Verlag, 2013, 25 (4), pp.523-535. 〈10.1007/s10878-011-9448-5〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00821598
Contributeur : Frederic Havet <>
Soumis le : dimanche 23 octobre 2016 - 16:00:10
Dernière modification le : mardi 10 octobre 2017 - 13:46:47

Fichier

3aretecol.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Stéphane Bessy, Frédéric Havet. Enumerating the edge-colourings and total colourings of a regular graph. Journal of Combinatorial Optimization, Springer Verlag, 2013, 25 (4), pp.523-535. 〈10.1007/s10878-011-9448-5〉. 〈hal-00821598〉

Partager

Métriques

Consultations de
la notice

243

Téléchargements du document

80