Minimum chromaticity of circulant graphs
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\).
- Circulants and their connectivities
- Coloring of integer distance graphs
- Colouring prime distance graphs
- Cyclic graphs
- Hamiltonian decomposition of Cayley graphs of degree 4
- Hardness results and spectral techniques for combinatorial problems on circulant graphs
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 4201663 (Why is no real title available?)
- Network properties of double and triple fixed step graphs
- On the chromatic number of special distance graphs
- On the spectral Ádám property for circulant graphs
- Recognizing circulant graphs in polynomial time: An application of association schemes
- The chromatic numbers of distance graphs
- On the chromatic number of circulant graphs
- On planarity and colorability of circulant graphs
- Vertex-colouring of 3-chromatic circulant graphs
- Achromatic numbers for circulant graphs and digraphs
- Chromatic number of circulant graph \(C_{n+1}\langle 1, 3\rangle\) after subdividing all or some of its edges
- The n-minimal chromatic multiplicity of a graph
- scientific article; zbMATH DE number 1454643 (Why is no real title available?)
- Density of Chromatic Roots in Minor-Closed Graph Families
- Achromatic and harmonious colorings of circulant graphs
- scientific article; zbMATH DE number 861338 (Why is no real title available?)
- Minors in Graphs with High Chromatic Number
- Colouring clique-hypergraphs of circulant graphs
- Computational Science and Its Applications – ICCSA 2004
- Colouring clique-hypergraphs of circulant graphs
- Disjoint path covers in recursive circulants G(2ᵐ,4) with faulty elements
This page was built for publication: Minimum chromaticity of circulant graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2568490)
