Vertex-colouring of 3-chromatic circulant graphs

A circulant graph C-n(a(l),..., a(k)) is a graph with n vertices {v(o),..., v(n-1)}such that each vertex v(i) is adjacent to vertices v((i+aj)) (mod n), 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(k(3)log(2)n + n) algorithm for a subclass of 3-chromatic C-n(a(l),..., a(k))'s with k >= 2, which are characterized in the paper. (C) 2017 Elsevier B.V. All rights reserved.