Bipartite finite Toeplitz graphs

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