Inclusion-Exclusion Based Algorithms for Graph Colouring.
Andreas Björklund, Thore Husfeldt · Electronic colloquium on computational complexity · 2006
We present a deterministic algorithm producing the number of k-colourings of a graph on n vertices in time 2nnO(1). We also show that the chromatic number can be found by a polynomial space algorithm running in time O(2.2461). Finally, we present a family of polynomial space approximation algorithms that find a number between χ(G) and (1 + )χ(G) in time O(1.2209 + 2.2461 − ).