Vertex-colouring of 3-chromatic circulant graphs

A circulant graph Cn(a1,…,ak) is a graph with n vertices {v0,…,vn−1} such that each vertex vi is adjacent to vertices v(i+aj)modn, for j=1,…,k. In this paper we investigate the vertex colouring problem on circulant graphs. We approach the problem in a purely combinatorial way based on an array representation and propose an exact O(k3log2n+n) algorithm for a subclass of 3-chromatic Cn(a1,…,ak)'s with k≥2, which are characterized in the paper.