Coloring planar Toeplitz graphs and the stable set polytope. (Q1422423)

The first part of the paper studies the coloring problem of planar Toeplitz graphs, i.e., graphs with vertex set \(\mathbb{N}\) where two vertices \(x\) and \(y\) are adjacent if and only if \(| x-y| \) is an element of a given set \(I=\{i_1,\ldots,i_m,\ldots\}\). If \(I=\{i_1,\ldots,i_m\}\) is finite, the associated Toeplitz graph is shown to have exactly \(\gcd(i_1,\ldots,i_m)\) connected and isomorphic components. A Toeplitz graph is shown to be planar if and only if \(I\subseteq \{1+i, 1+j, 1+i+j\}\) for some nonnegative integers \(i\) and \(j\). If the Toeplitz graph is planar with \(I=\{1+i,1+j,1+i+j\}\) and \(i<j\), denote the highest power of \(3\) dividing \(i\) by \(3^r\). Then it is shown that this Toeplitz graph is \(3\)-colorable if and only if \(3^{r+1}\) divides \(j-i\). Since all planar graphs are \(4\)-colorable and bipartite Toeplitz graphs have been characterized in [\textit{R. Euler}, \textit{H. Le Verge} and \textit{T. Zamfirescu}, A characterization of infinite, bipartite Toeplitz graphs, in: Combinatorics and graph theory '95, Vol. 1, 119--130 (1995)] the chromatic number of any planar Toeplitz graph can easily be determined. It turns out that if a planar Toeplitz graph is not \(3\)-colorable, then it contains a so-called \((K_4 \setminus e)\)-cycle as a subgraph: Let \((K_n\setminus e)\) be the complete graph on \(n\) vertices with one edge removed, and let \(a\) and \(b\) denote the vertices of degree \(n-2\), which are called the distinguished vertices. A collection \((K^1,K^2,\ldots, K^m)\) of such \((K_n\setminus e)\)'s is called a \((K_n\setminus e)\)-cycle \(C\), if \(K^i\) and \(K^{i+1}\) have one of their distinguished vertices in common, i.e., \(b_i=a_{i+1}\) for \(i=1,\ldots, m-1\), and possibly \(n-3\) of its neighbors; finally, \(a_1\) and \(b_m\) are connected by an edge. Such a \((K_n\setminus e)\)-cycle \(C\) is easily seen to be \(n\)-critical with respect to coloring. Thus such a cycle may be seen as a common generalization of odd cycles and cliques. The second part of the paper exhibits a facet defining inequality for the stable set polytope of a \((K_n\setminus E)\)-cycle, i.e., the convex hull of the incidence vectors of its stable sets. Finally it is shown how Hajós' construction can be used to further generalize \((K_n\setminus e)\)-cycles thereby providing a very large class of \(n\)-critical graphs which are still facet-inducing for the associated stable set polytope.