On the chromatic number of integral circulant graphs

ntegral circulant graphs are a generalization of unitary Cayley graphs, recently studied by Klotz and Sander. The integral circulant graph Xn.D/ has vertices 0; 1; : : : ; n 􀀀 1, and two vertices a and b are adjacent iff gcd.x 􀀀 y; n/ 2 D, where D fd V d j n; 1 d < ng. Circulant graphs have various applications in the design of interconnection networks in parallel and distributed computing, while integral graphs play an important role in modeling quantum spin networks supporting the perfect state transfer. Integral circulant graphs also found applications in molecular graph energy. In this paper we deal with the chromatic number of integral circulant graphs and investigate the conjecture proposed in [W. Klotz, T. Sander, Some properties of unitary Cayley graphs, Electron. J. Combin. 14 (2007) #R45] that the chromatic number divides the order of Xn.D/. For the integral circulant graph with two divisors, sharp upper and lower bounds for the chromatic number are established; if one of the divisors is equal to one, the chromatic number is explicitly determined. For jDj 3, we construct a family of counterexamples using exhaustive search algorithm for graph coloring and disprove the conjecture in this case.