Barajas, Javier; Serra, Oriol On the chromatic number of circulant graphs. (English) Zbl 1213.05064 Discrete Math. 309, No. 18, 5687-5696 (2009). Summary: Given a set \(D\) of a cyclic group \(C\), we study the chromatic number of the circulant graph \(G(C,D)\) whose vertex set is \(C\), and there is an edge \(ij\) whenever \(i - j\in D\cup - D\). For a fixed set \(D=\{a,b,c:a<b<c\}\) of positive integers, we compute the chromatic number of circulant graphs \(G(\mathbb Z_N,D)\) for all \(N\geq 4bc\). We also show that, if there is a total order of \(D\) such that the greatest common divisors of the initial segments form a decreasing sequence, then the chromatic number of \(G(\mathbb Z,D)\) is at most 4. In particular, the chromatic number of a circulant graph on \(\mathbb Z_N\) with respect to a minimum generating set \(D\) is at most 4. The results are based on the study of the so-called regular chromatic number, an easier parameter to compute. The paper also surveys known results on the chromatic number of circulant graphs. Cited in 1 ReviewCited in 14 Documents MSC: 05C15 Coloring of graphs and hypergraphs Keywords:circulant graphs; chromatic number × Cite Format Result Cite Review PDF Full Text: DOI References: [1] Babai, L.; Sós, V. T., Sidon sets in groups and induced subgraphs of Cayley graphs, European J. Combin., 6, 101-114 (1985) · Zbl 0573.05032 [2] Barajas, J.; Serra, O., Distance graphs with maximum chromatic number, Discrete Math., 308, 1355-1365 (2008) · Zbl 1136.05018 [3] Barajas, J.; Serra, O., The lonely runner with seven runners, Electron. J. Combin., 15, 1, R48 (2008) · Zbl 1206.11030 [4] Betke, U.; Wills, J. M., Untere Schranken für zwei dophantische approximations-Funktionen, Monatsch. Math., 76, 214-217 (1972) · Zbl 0239.10016 [5] Biennia, W.; Goddyn, L.; Gvozdjak, P.; Sebő, A.; Tarsi, M., Flows, view obstructions and the lonely runner, J. Combin. Theory Ser. B, 72, 1-9 (1998) · Zbl 0910.05064 [6] Bohman, T.; Holzman, R.; Kleitman, D., Six lonely runners, Electron. J. Combin., 8, 2 (2001), Research Paper 3, 49 pp · Zbl 1011.11048 [7] Chang, G. J.; Huang, L.; Zhu, X., Circular chromatic number and fractional chromatic numbers of distance graphs, European J. Combin., 19, 423-431 (1998) · Zbl 0905.05032 [8] Chen, Y. G., On a conjecture about diophantine approximations III, J. Number Theory, 39, 91-103 (1991) · Zbl 0732.11032 [9] Chen, Y. G., On a conjecture about diophantine approximations IV, J. Number Theory, 43, 186-197 (1993) · Zbl 0769.11029 [10] Chen, J.; Chang, G.; Huang, K., Integral distance graphs, J. Graph Theory, 25, 281-287 (1997) · Zbl 0878.05028 [11] Chen, Y. G.; Cusick, T. W., The view-obstruction problem for \(n\)-dimensional cubes, J. Number Theory, 74, 126-133 (1999) · Zbl 0921.11030 [12] Codenotti, B.; Gerace, I.; Vigna, S., Hardness results and spectral techniques for combinatorial problems on circulant graphs, Linear Algebra Appl., 285, 123-142 (1998) · Zbl 0931.05050 [13] Cusick, T. W.; Pomerance, C., View obstruction problems III, J. Number Theory, 19, 131-139 (1984) · Zbl 0563.10026 [14] Cusick, T. W., View-obstruction problems, Aequationes Math., 9, 165-170 (1973) · Zbl 0265.52003 [15] Cusick, T. W., View-obstruction problems in \(n\)-dimensional geometry, J. Combin. Theory Ser. A, 16, 1-11 (1974) · Zbl 0273.10025 [16] Cusick, T. W., View-obstruction problems II, Proc. Amer. Math. Soc., 84, 25-28 (1982) · Zbl 0474.10023 [17] Deuber, W.; Zhu, X., The chromatic number of distance graphs, Discrete Math., 165-166, 195-204 (1997) · Zbl 0879.05027 [18] Eggleton, R. B.; Erdős, P.; Skilton, D. K., Colouring the real line, J. Combin. Theory Ser. B, 39, 86-100 (1985) · Zbl 0549.05029 [19] Eggleton, R. B.; Erdős, P.; Skilton, D. K., Coloring prime distance graphs, Graphs Combin., 6, 17-32 (1990) · Zbl 0698.05033 [20] Ferrara, M.; Kohayakawa, Y.; Rödl, V., Distance graphs on the integers, Combin. Probab. Comput., 14, 107-131 (2005) · Zbl 1061.05065 [21] Heuberger, C., On planarity and colorability of circulant graphs, Discrete Math., 268, 153-169 (2003) · Zbl 1028.05024 [22] Katznelson, Y., Chromatic number of Cayley graphs on \(Z\) and recurrence, Combinatorica, 21, 211-219 (2001) · Zbl 0981.05038 [23] Kemnitz, A.; Marangio, M., Colorings and list colorings of integer distance graphs, (Proceedings of the Thirty-Second Southeastern International Conference on Combinatorics, Graph Theory and Computing. Proceedings of the Thirty-Second Southeastern International Conference on Combinatorics, Graph Theory and Computing, Baton Rouge, LA, 2001. Proceedings of the Thirty-Second Southeastern International Conference on Combinatorics, Graph Theory and Computing. Proceedings of the Thirty-Second Southeastern International Conference on Combinatorics, Graph Theory and Computing, Baton Rouge, LA, 2001, Congr. Numer., vol. 151 (2001)), 75-84 · Zbl 0989.05039 [24] Kemnitz, A.; Marangio, M., Chromatic number of integer distance graphs, Discrete Math., 233, 239-246 (2001) · Zbl 0988.05039 [25] Lin, W.; Lam, P. C.B.; Song, Z., Circular chromatic numbers of some distance graphs, Discrete Math., 292, 119-130 (2005) · Zbl 1063.05045 [26] Liu, D. D.F.; Zhu, X., Fractional chromatic number and circular chromatic number for distance graphs with large clique size, J. Graph Theory, 47, 129-146 (2004) · Zbl 1055.05059 [27] Liu, D. D.F.; Zhu, X., Distance graphs with missing multiples in the distance sets, J. Graph Theory, 30, 245-259 (1999) · Zbl 0915.05056 [28] Meszka, M.; Nedela, R.; Rosa, A., Circulants and the chromatic index of steiner triple systems, Math. Slovaca, 56, 371-378 (2006) · Zbl 1141.05023 [29] M. Meszka, R. Nedela, A. Rosa, preprint 2007; M. Meszka, R. Nedela, A. Rosa, preprint 2007 [30] Obradović, N.; Peters, J.; Ružić, G., Minimum chromaticity of circulant graphs, Discrete Math., 299, 288-296 (2005) · Zbl 1081.05037 [31] Renault, J., View-obstruction: A shorter proof for 6 lonely runners, Discrete Math., 287, 93-101 (2004) · Zbl 1061.11036 [32] Ruzsa, I. Z.; Tuza, Zs.; Voigt, M., Distance graphs with finite chromatic number, J. Combin. Theory, Series B, 85, 181-187 (2002) · Zbl 1027.05036 [33] R. Soták, On a problem concerning integer distance graphs, manuscript, 2005; R. Soták, On a problem concerning integer distance graphs, manuscript, 2005 [34] Voigt, M., Coloring of distance graphs, Ars Combin., 52, 3-12 (1999) · Zbl 0977.05047 [35] Wills, J. M.; Säzte über, Zwei, inhomogene diophantische approximation von irrationalzahlen, Monatsch. Math., 71, 263-269 (1967) · Zbl 0148.27505 [36] Yeh, H. G.; Zhu, X., 4-colourable 6-regular toroidal graphs, Discrete Math., 273, 261-274 (2003) · Zbl 1034.05024 [37] Zhu, X., Circular chromatic number of distance graphs with distance sets of cardinality 3, J. Graph Theory, 41, 195-207 (2002) · Zbl 1012.05071 [38] Zhu, X., Pattern periodic coloring of distance graphs, J. Combin. Theory Ser. B, 73, 195-206 (1998) · Zbl 0904.05028 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.