𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The stable set polytope of quasi-line graphs

✍ Scribed by Friedrich Eisenbrand; Gianpaolo Oriolo; Gautier Stauffer; Paolo Ventura

Publisher
Springer-Verlag
Year
2008
Tongue
English
Weight
342 KB
Volume
28
Category
Article
ISSN
0209-9683

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Clique family inequalities for the stabl
Clique family inequalities for the stable set polytope of quasi-line graphs
✍ G. Oriolo πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 248 KB

In one of fundamental works in combinatorial optimization, Edmonds gave a complete linear description of the matching polytope. Matchings in a graph are equivalent to stable sets in its line graph. Also the neighborhood of any vertex in a line graph partitions into two cliques: graphs with this latt

Coloring planar Toeplitz graphs and the
Coloring planar Toeplitz graphs and the stable set polytope
✍ Reinhardt Euler πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 290 KB

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

Stability critical graphs and ranks face
Stability critical graphs and ranks facets of the stable set polytope
✍ E.C. Sewell; L.E. Trotter Jr. πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 616 KB

Rank inequalities due to stability critical (u-critical) graphs are used to develop a finite nested sequence of linear relaxations of the stable set polytope, the strongest of which provides an integral max-min relation: In a simple graph, the maximum size of a stable set is equal to the minimum (we