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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Coloring planar Toeplitz graphs and the stable set polytope.
scientific article

    Statements

    Coloring planar Toeplitz graphs and the stable set polytope. (English)
    0 references
    0 references
    14 February 2004
    0 references
    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.
    0 references
    chromatic number
    0 references
    odd cycles
    0 references
    cliques
    0 references

    Identifiers