Coloring planar Toeplitz graphs and the stable set polytope.
type: Item
instance of: scholarly article
title: Coloring planar Toeplitz graphs and the stable set polytope.
zbMATH Open document ID: 1039.05030
DOI: 10.1016/S0012-365X(03)00315-7
author: Reinhardt Euler
published in: Discrete Mathematics
publication date: 2004-02-14T00:00:00Z
review text: 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 o…
reviewed by: Clemens Heuberger
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 2041905
zbMATH Keywords: chromatic number
zbMATH Keywords: odd cycles
zbMATH Keywords: cliques
MaRDI profile type: Publication
cites work: Q5422499
cites work: Efficiently solvable special cases of bottleneck travelling salesman problems
cites work: Integral distance graphs
cites work: On certain polytopes associated with graphs
cites work: The chromatic numbers of distance graphs
cites work: Colouring the real line
cites work: Colouring prime distance graphs
cites work: Characterizing bipartite Toeplitz graphs
cites work: Q4414636
cites work: Q4198056
cites work: On hamiltonian Toeplitz graphs
cites work: On planarity and colorability of circulant graphs
cites work: 25 pretty graph colouring problems
cites work: Chromatic numbers of integer distance graphs
cites work: Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
cites work: On the facial structure of set packing polyhedra
cites work: On critical edges in minimal imperfect graphs
cites work: Hamiltonian properties of Toeplitz graphs
cites work: Hamiltonian cycles in circulant digraphs with two stripes
cites work: Q4014311
description: scientific article; zbMATH DE number 2041905