Deterministic counting of graph colourings using sequences of subgraphs

Charilaos Efthymiou

In this paper we propose a deterministic algorithm for approximately counting the $k$-colourings of sparse random graphs $G(n,d/n)$. In particular, our algorithm computes in polyno…