Coloring Planar Toeplitz Graphs

We study structural properties of infinite Toeplitz graphs such as connectivity, planarity and colorability. As to connectivity we show that any infinite Toeplitz graph decomposes into a finite number of connected and isomorphic components. Similar to the bipartite case (cf. [4]), infinite planar Toeplitz graphs can be characterized by a simple condition on their defining 0-1 sequence. We then turn to the problem of coloring such planar graphs. Whereas they can always be 4-colored by a greedy-like algorithm, we are able to fully characterize the subclass of 3-colorable such graphs. As a corollary we obtain a Konig-type characterization of this class by means of (K4\e)-cycles, a family of 4-critical graphs that generalize odd cycles. We also discuss some consequences for general (finite) graph coloring.