Vertex-colouring of circulant graphs: a combinatorial approach

Consider three integers $n,a,b$ such that $n>0$, $a \bmod n \neq 0$, $b \bmod n \neq 0$, and $a \bmod n \neq \pm b \bmod n$. The graph $C_n(a,b)=(V,E)$, where $V = \{v_0, v_1, \dots, v_{n-1}\}$ and $E = \{(v_i,v_{(i+a)\bmod n})$, $ (v_i,v_{(i+b)\bmod n})$, for $i=0, \dots, n-1 )\}$ is called {\em circulant graph}. In this paper we propose exact linear algorithms for {\sc vertex-colouring}: given an arbitrary circulant graph $C_n(a,b)$, find an assignment of colours to its vertices such that adjacent vertices receive different colours and the number of colours is minimized. The approach is purely combinatorial and new for the topic: it is based on a suitable matrix representation of an arbitrary $C_n(a,b)$, which highlights the strong topological properties of its cycles, and allows the design of very simple colouring algorithms.