Andreas Björklund, Thore Husfeldt

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

Siddharth Bhandari, Sayantan Chakraborty

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