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.

Un grafo circolante C-n(a(l),..., a(k)) è un grafo con n nodi {v(o),..., v(n-1)} in uni ogni nodo v(i) è adiacente ai nodi v((i+aj)) (mod n), for j = 1, ..., k. In questo articolo noi affrontiamo il problema della colorazione dei nodi di un grafo circolante. Il problema viene visto da un punto di vista puramente combinatorio e si basa su una rappresentazione matriciale del grafo. Nel lavoro viene proposto un algoritmo esatto O(k(3)log(2)n + n) per una sottoclasse di grafi circolanti 3-cromatici C-n(a(l),..., a(k)) con k >= 2, caratterizzata nell'articolo.