Coloring Circulant Graphs

Let n, a and b be positive integers. By Cn(a,b)=(V,E) we shall denote the graph on n = |V| vertices whose edge set is E = {(i,(i+a) mod n), (i,(i-a) mod n), (i,(i+b) mod n), (i,(i-b) mod n), for i = 0, ..., n-1}. The problem we deal with is the following Given three positive integers n, a and b, such that the (simple) graph Cn(a,b) is 4-regular and connected Find an assignment of colors to the vertices of Cn(a,b) Such That adjacent vertices receive different colors and the number ?(Cn(a,b)) of used colors is minimized. We discuss some simple isomorphism conditions, we characterize ?(Cn(a,b)) on the basis of simple relations between n, a, b, and propose linear algorithms for determining optimum colorings. Effective mathematical models are proposed, and the structure of some characteristic cycles of the graphs is investigated.