Enumerating the edge-colourings and total colourings of a regular graph - Archive ouverte HAL Access content directly
Journal Articles Journal of Combinatorial Optimization Year : 2013

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

(1) , (2)
1
2
Stéphane Bessy
Frédéric Havet

#### 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.

#### Domains

Computer Science [cs] Discrete Mathematics [cs.DM]

### Dates and versions

hal-00821598 , version 1 (23-10-2016)

### Identifiers

• HAL Id : hal-00821598 , version 1
• DOI :

### Cite

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

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

234 View