On planarity and colorability of circulant graphs Original Research Article

For given positive integers n,a1,…,am, we consider the undirected circulant graph G=(V,E) with set of vertices V={0,…,n−1} and set of edges E={[i,j]: i−j≡±ak (mod n) for some 1⩽k⩽m}. We prove that G is planar if m=1 and non-planar if m⩾3. For m=2 we completely characterize planarity. It is shown that G is bipartite if and only if there is an l such that 2l divides a1,…,am, 2l+1|n, but 2l+1∤aj for 1⩽j⩽m. If m⩽2, we also calculate the chromatic number of G.