Stable sets and polynomials
type: Item
instance of: scholarly article
title: Stable sets and polynomials
zbMATH Open document ID: 0792.05082
DOI: 10.1016/0012-365X(92)00057-X
published in: Discrete Mathematics
publication date: 1994-03-01T00:00:00Z
review text: The author surveys various applications of methods involving nonlinear commutative algebra to the stable set problem for graphs. In particular, he discusses a procedure for generating the facets of the stable set polytope. If a class of graphs \(G\) is such that all the facets of the stable set polytopes can be generated this way in a bounded number of steps, then the stability numbers of these graphs \(G\) are computable in polynomial time. Perfect, \(t\)-perfect, and \(h\)-perfect graphs have this property.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 500614
zbMATH Keywords: polynomials
zbMATH Keywords: stable set problem
zbMATH Keywords: facets
zbMATH Keywords: stable set polytope
zbMATH Keywords: stability numbers
reviewed by: J. W. Moon
MaRDI profile type: Publication
cites work: Colorings and orientations of graphs
cites work: Q5572947
cites work: The perfectly matchable subgraph polytope of an arbitrary graph
cites work: Compositions of Graphs and Polyhedra II: Stable Sets
cites work: Q3941433
cites work: On certain polytopes associated with graphs
cites work: Q3284375
cites work: A Problem in Graph Theory
cites work: Relaxations of vertex packing
cites work: Geometric algorithms and combinatorial optimization
cites work: A Theorem on k-Saturated Graphs
cites work: Independence numbers of graphs and generators of ideals
cites work: Q4133994
cites work: Q4163239
cites work: On the Shannon capacity of a graph
cites work: Matching theory
cites work: Q3973406
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: Maxima for Graphs and a New Proof of a Theorem of Turán
cites work: Stability critical graphs and ranks facets of the stable set polytope
cites work: A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
cites work: Combinatorics and commutative algebra
Recommended article: Q3481820
Recommended article: On stable and fixed polynomials
Recommended article: Polynomials on stable spaces
Recommended article: Some remarks on stable polynomials
Recommended article: Q3033657
Recommended article: Q3435504
Recommended article: Stable polynomials over finite fields
Recommended article: Stabilité des polynômes
Recommended article: Q3710427
Recommended article: Q4838260
author: László Lovász
description: scientific article; zbMATH DE number 500614