On stable set polyhedra for K//(1,3)free graphs

DOI10.1016/0095-8956(81)90033-2zbMath0494.05032OpenAlexW2039986023MaRDI QIDQ1168982

Rick Giles, Leslie E. jun. Trotter

Publication date: 1981

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(81)90033-2

zbMATH Keywords

stable setstrong perfect graph conjecturefacet

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (37)

Vertex packing problem application to the design of electronic testing fixtures ⋮ Lift-and-project ranks of the stable set polytope of joined \(a\)-perfect graphs ⋮ Small Chvátal rank ⋮ Claw-free graphs---a survey ⋮ A construction for non-rank facets of stable set polytopes of webs ⋮ Applying Lehman's theorems to packing problems ⋮ On cutting-plane proofs in combinatorial optimization ⋮ On the facets of stable set polytopes of circular interval graphs ⋮ On the complete set packing and set partitioning polytopes: properties and rank 1 facets ⋮ The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect ⋮ The stable set polytope of icosahedral graphs ⋮ On the facets of the stable set polytope of quasi-line graphs ⋮ Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs ⋮ An approach to solving \(A^{k}=J-I\) ⋮ Clique family inequalities for the stable set polytope of quasi-line graphs. ⋮ 2-clique-bond of stable set polyhedra ⋮ A note on the Chvátal-rank of clique family inequalities ⋮ Clique-circulants and the stable set polytope of fuzzy circular interval graphs ⋮ The stable set polytope of quasi-line graphs ⋮ Lifted, projected and subgraph-induced inequalities for the representatives \(k\)-fold coloring polytope ⋮ On the mixed set covering, packing and partitioning polytope ⋮ Extended formulations in combinatorial optimization ⋮ On facets of stable set polytopes of claw-free graphs with stability number 3 ⋮ Extended formulations in combinatorial optimization ⋮ Unnamed Item ⋮ On non-rank facets of stable set polytopes of webs with clique number four ⋮ Gear composition and the stable set polytope ⋮ Strengthened clique-family inequalities for the stable set polytope ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lovász-Schrijver PSD-Operator on Claw-Free Graphs ⋮ On the Stable Set Polytope of Claw-Free Graphs ⋮ Almost all webs are not rank-perfect ⋮ Generalized clique family inequalities for claw-free graphs ⋮ On facets of stable set polytopes of claw-free graphs with stability number three ⋮ The maximum clique problem ⋮ Total coloring of quasi-line graphs and inflated graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphical properties related to minimal imperfection
• On maximal independent sets of vertices in claw-free graphs
• Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs
• The strong perfect-graph conjecture is true for \(K_{1,3}\)-free graphs
• A class of facet producing graphs for vertex packing polyhedra
• Almost integral polyhedra related to certain combinatorial optimization problems
• Critical perfect graphs and perfect 3-chromatic graphs
• Anti-blocking polyhedra
• A characterization of perfect graphs
• Normal hypergraphs and the perfect graph conjecture
• Edmonds polytopes and a hierarchy of combinatorial problems
• Coloring a Family of Circular Arcs
• Properties of vertex packing and independence system polyhedra
• Perfect zero–one matrices
• On the facial structure of set packing polyhedra
• Maximum matching and a polyhedron with 0,1-vertices
• On the strong perfect graph conjecture

This page was built for publication: On stable set polyhedra for K//(1,3)free graphs