Bipartite finite Toeplitz graphs

Let n,a1,…,akn,a1,…,ak be distinct positive integers. A finite Toeplitz graph Tn(a1,…,ak)=(V,E)Tn(a1,…,ak)=(V,E) is a graph where V={v0,…,vn−1}V={v0,…,vn−1} and E={(vi,vj):|i−j|∈{a1,…,ak}}E={(vi,vj):|i−j|∈{a1,…,ak}}. In this paper, we characterize bipartite finite Toeplitz graphs with k≤3k≤3. In most cases, the characterization takes O(loga3)O(loga3) arithmetic steps; in the remaining cases, it takes O(a1)O(a1). A consequence of the proposed results is the complete characterization of the chromatic number of finite Toeplitz graphs with k≤3k≤3. In addition, we characterize some classes of infinite bipartite Toeplitz graphs with k≥4k≥4.