Coloring planar Toeplitz graphs and the stable set polytope

✍ Scribed by Reinhardt Euler

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 290 KB
• Volume: 276
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(03)00315-7

✦ Synopsis

Cliques and odd cycles are well known to induce facet-deÿning inequalities for the stable set polytope. In graph coloring cliques are a class of n-critical graphs whereas odd cycles represent the class of 3-critical graphs. In the ÿrst part of this paper we generalize both notions to (Kn \ e)-cycles, a new class of n-critical graphs, and discuss some implications for the class of inÿnite planar Toeplitz graphs. More precisely, we show that any inÿnite Toeplitz graph decomposes into a ÿnite number of connected and isomorphic components. Similar to the bipartite case, inÿnite planar Toeplitz graphs can be characterized by a simple condition on their deÿning 0 -1 sequence. We then address the problem of coloring such graphs. Whereas they can always be 4-colored by a greedy-like algorithm, we are able to fully characterize the subclass of 3-chromatic such graphs. As a corollary, we obtain a K onig-type characterization of this class by means of (K4 \ e)-cycles. In the second part, we turn to polyhedral theory and show that (Kn \ e)-cycles give rise to a new class of facet-deÿning inequalities for the stable set polytope. Then we show how Hajà os' construction can be used to further generalize (Kn \ e)-cycles thereby providing a very large class of n-critical graphs which are still facet-inducing for the associated stable set polytope.