Vertex-Colouring of Some 3-Chromatic Circulant Graphs $C_N(A,B,C)$ Where $3|\Gcd(N,A)$

作     者：Nicoloso, Sara 

作者机构：IASI CNR Via dei Taurini 19 Roma00185 Italy 

出 版 物：《SSRN》 

年 卷 期：2025年

核心收录：

主　　题：Graph algorithms 

摘      要：A circulant graph $C_n(a,b,c)$ is the graph with $n$ vertices $\{v_0, \dots, v_{n-1}\}$ such that each vertex $v_i$ is adjacent to vertices $v_{(i+ a) \bmod n}$, $v_{(i+ b) \bmod n}$, $v_{(i+ c) \bmod n}$. The vertex-colouring problem consists in finding an assignment of colours to the vertices of a given graph in such a way that adjacent vertices receive different colours and the number of colours is minimized. In this paper we approach the 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 the connected 3-chromatic circulant graphs $C_n(a,b,c)$ verifying $3|\gcd(n,a)$. © 2025, The Authors. All rights reserved.