Critical facets of the stable set polytope

Citation
L. Liptak et L. Lovasz, Critical facets of the stable set polytope, COMBINATORI, 21(1), 2001, pp. 61-88
Citations number
13
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics,"Computer Science & Engineering
Journal title
COMBINATORICA
ISSN journal
0209-9683 → ACNP
Volume
21
Issue
1
Year of publication
2001
Pages
61 - 88
Database
ISI
SICI code
0209-9683(2001)21:1<61:CFOTSS>2.0.ZU;2-R
Abstract
A facet of the stable set polytope of a graph G can be viewed as a generali zation of the notion of an alpha -critical graph. We extend several results from the theory of alpha -critical graphs to facets. The defect of a nontr ivial, full-dimensional facet Sigma (v is an element ofV) a(v)x(v) less tha n or equal to b of the stable set polytope of a graph G is defined by delta = Sigma (v is an element ofV) a(v) - 2b. We prove the upper bound a(u) + d elta for the degree of any node u in a critical facet-graph, and show that d(u)= 2 delta can occur only when delta = 1. We also give a simple proof of the characterization of critical facet-graphs with defect 2 proved by Sewe ll [11]. As an application of these techniques we sharpen a result of Suran yi [13] by showing that if an alpha -critical graph has defect delta and co ntains delta + 2 nodes of degree delta + 1, then the graph is an odd subdiv ision of Kdelta +2.