Cliques, holes and the vertex coloring polytope

Certain subgraphs of a given graph G restrict the minimum number chi(G) of colors that can be assigned to the vertices of G such that the endpoints of all edges receive distinct colors. Some of such subgraphs are related to the celebrated Strong Perfect Graph Theorem. as it implies that every graph G contains a clique of size chi(G), or an odd hole or an odd anti-hole as an induced subgraph. In this paper, we investigate the impact of induced maximal cliques, odd holes and odd anti-holes on the polytope associated with a new 0-1 integer programming formulation of the graph coloring problem. We show that they induce classes of facet defining, inequalities. (C) 2003 Elsevier B.V. All rights reserved.