Vertex-colouring of some 3-chromatic circulant graphs Cn(a,b,c) where 3|gcd(n,a)

A circulant graph C n ( a , b , c ) is a graph with n vertices { v 0 , … , v n − 1 } in which each vertex v i is adjacent to the vertices v ( i + a ) mod n , v ( i + b ) mod n , and v ( i + c ) mod n . The vertex colouring problem consists of assigning colours to the vertices of a graph so that adjacent vertices receive different colours, while minimizing the number of colours used. In this paper, we study this problem in a purely combinatorial way, based on an array representation of the graph, and propose exact linear-time vertex-colouring algorithms for a subclass of connected 3-chromatic circulant graphs C n ( a , b , c ) satisfying 3 | gcd ( n , a ) .