On the chromatic number of Toeplitz graphs

Let n,a1,a2,…,akn,a1,a2,…,ak be distinct positive integers. A finite Toeplitz graph Tn(a1,a2,…,ak)=(V,E)Tn(a1,a2,…,ak)=(V,E) is a graph where V={v0,v1,…,vn−1}V={v0,v1,…,vn−1} and E={vivj,  for  |i−j|∈{a1,a2,…,ak}}E={vivj,  for  |i−j|∈{a1,a2,…,ak}}. In this paper, we first refine some previous results on the connectivity of finite Toeplitz graphs with k=2k=2, and then focus on Toeplitz graphs with k=3k=3, proving some results about their chromatic number.

► We characterize the 3- and 4-chromatic Toeplitz graphs Tn(a,b,c)Tn(a,b,c) with three entries. ► Depending on a,b,ca,b,c, we compute μμ such that χ(Tn(a,b,c))=3χ(Tn(a,b,c))=3 iff n≤μ−1n≤μ−1. ► The characterization is obtained by means of forbidden subgraphs. ► We refine some results on the connectivity of Toeplitz graphs with two entries.