Minimum chromaticity of circulant graphs (Q2568490)

If \(S=\{s_1,s_2,\dots,s_k\}\) is a set of natural numbers then the circulant graph \(G=G^c(n;S)\) is a graph with vertex set \(V=\{v_0,v_1,\dots,v_{n-1}\}\) and the edge set consisting of edges of the form \(\{v_j,v_{j+s_k \text{mod} n}\}\) where \(s_k\) is a member of \(S\). A geometric circulant graph \(G=GG^c(n;d)\) is a circulant graph with \(S=\{d^0,d^1,\dots,d^m\}\) for \(1<d\leq\frac n2\) and \(m\) satisfying the condition \(d^m+1<n\leq d^{m+1}+1\). A recursive circulant graph \(RG^c(n;d)\) is a geometric circulant graph with order \(n=cd^m\), \(1<c\leq d\). It is shown that for \(d\neq 2\) every recursive circulant graph \(G\) has \(\chi(G)\leq 3\). Moreover it is proved that there exists \(n_0\) such that \(\chi(G)\leq 3\) for all circulant graphs \(G^c(n;S)\) with \(S\) satisfying \(s_k>s_{k-1}>\cdots>s_1\) and \(2s_1>s_k\) or \(S=\{s_1,s_2\}\) and \(s_2>s_1\geq 1\) and \(s_2\neq 2s_1\).