We present a deterministic algorithm producing the number of
k-colourings of a graph on n vertices in time
2^nn^{O(1)}.
We also show that the chromatic number can be found by a
polynomial space algorithm running in time O(2.2461^n).
Finally, we present a family of ... more >>>

We present a randomized algorithm that takes as input an undirected n-vertex graph G with maximum degree \Delta and an integer k > 3\Delta, and returns a random proper k-coloring of G. The
distribution of the coloring is perfectly uniform over the set of all proper k-colorings; ... more >>>