Search

A main result of combinatorial optimization is that the clique and chromatic numbers of a perfect graph are computable in polynomial time (Grötschel et al., 1981) [7]. This result relies on polyhedral characterizations of perfect graphs involving the stable set polytope of the graph, a linear relaxation defined by clique constraints, and a semi-definite relaxation, the Theta-body of the graph. A natural question is whether the algorithmic results for perfect graphs can be extended to graph classes with similar polyhedral properties. We consider a superclass of perfect graphs, the -perfect graphs, whose stable set polytope is given by constraints associated with generalized cliques. We show that for such graphs the clique number can be computed in polynomial time as well. The result strongly relies upon Fulkerson’s antiblocking theory for polyhedra and Lovász’s Theta function. [ABSTRACT FROM AUTHOR]

Abstract: Graphs with circular symmetry, called webs, are relevant w.r.t. describing the stable set polytopes of two larger graph classes, quasi-line graphs [G. Giles, L.E. Trotter Jr., On stable set polyhedra for -free graphs, J. Combin. Theory B 31 (1981) 313–326; G. Oriolo, Clique family inequalities for the stable set polytope for quasi-line graphs, in: Stability Problems, Discrete Appl. Math. 132 (2003) 185–201 (special issue)] and claw-free graphs [A. Galluccio, A. Sassano, The rank facets of the stable set polytope for claw-free graphs, J. Combin. Theory B 69 (1997) 1–38; G. Giles, L.E. Trotter Jr., On stable set polyhedra for -free graphs, J. Combin. Theory B 31 (1981) 313–326]. Providing a decent linear description of the stable set polytopes of claw-free graphs is a long-standing problem [M. Grötschel, L. Lovász, A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, 1988]. However, even the problem of finding all facets of stable set polytopes of webs is open. So far, it is only known that stable set polytopes of webs with clique number have rank facets only [G. Dahl, Stable set polytopes for a class of circulant graphs, SIAM J. Optim. 9 (1999) 493–503; L.E. Trotter, Jr., A class of facet producing graphs for vertex packing polyhedra, Discrete Math. 12 (1975) 373–388] while there are examples with clique number having non-rank facets [J. Kind, Mobilitätsmodelle für zellulare Mobilfunknetze: Produktformen und Blockierung, Ph.D. Thesis, RWTH Aachen, 2000; T.M. Liebling, G. Oriolo, B. Spille, G. Stauffer, On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs, Math. Methods Oper. Res. 59 (2004) 25; G. Oriolo, Clique family inequalities for the stable set polytope for quasi-line graphs, in: Stability Problems, Discrete Appl. Math. 132 (2003) 185–201 (special issue); A. Pêcher, A. Wagler, On non-rank facets of stable set polytopes of webs with clique number four, Discrete Appl. Math. 154 (2006) 1408–1415]. In this paper, we provide a construction for non-rank facets of stable set polytopes of webs. This construction is the main tool to obtain in a companion paper [A. Pêcher, A. Wagler, Almost all webs are not rank-perfect, Math. Program 105 (2006) 311–328], for all fixed values of that there are only finitely many webs with clique number whose stable set polytopes admit rank facets only. [Copyright &y& Elsevier]

Circular-perfect graphs form a natural superclass of perfect graphs, introduced by Zhu almost 20 years ago: on the one hand due to their definition by means of a more general coloring concept, on the other hand as an important class of χ -bound graphs with the smallest non-trivial χ -binding function χ (G) ≤ ω (G) + 1. In this paper, we survey the results about circular-perfect graphs obtained in the two last decades, with a focus on whether the fascinating properties of perfect graphs can be extended to this superclass. We recall the deep algorithmic properties of perfect graphs and the underlying polyhedral graph theory, in order to outline in this setting the main graph parameters that are also related to circular-perfect graphs. Finally, we give a list of open problems. [ABSTRACT FROM AUTHOR]