On the chromatic number of circulant graphs

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 i j whenever i − j ∈ D ∪ − D . For a fixed set D = { a , b , c : a < b < c } of positive integers, we compute the chromatic number of circulant graphs G ( Z N , D ) for all N ≥ 4 b c . 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 ( Z , D ) is at most 4. In particular, the chromatic number of a circulant graph on 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.