Vertex-colouring of 3-chromatic circulant graphs

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.