Stable sets and polynomials. (English) Zbl 0792.05082
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.
Reviewer: J.W.Moon (Edmonton)
References:
| [1] | Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 125-134 (1992) · Zbl 0756.05049 |
| [2] | Andrásfai, B., On critical graphs, (Rosenstiehl, P., Int. Symp. on Theory of Graphs, Rome (1966), Gordon and Breach: Gordon and Breach New York), 9-19 · Zbl 0182.58001 |
| [3] | Balas, E.; Pulleyblank, W. R., The perfect matchable subgraph polytope of an arbitrary graph, Combinatorica, 9, 321-337 (1989) · Zbl 0723.05087 |
| [4] | Barahona, F.; Mahjoub, A. R., Compositions of graphs and polyhedra II: stable sets, (Res. Report 87464-OR (1987), Univ. of Bonn) · Zbl 0802.05068 |
| [5] | Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029 |
| [6] | Chvátal, V., On certain polytopes associated with graphs, J. Combin. Theory Ser. B, 13, 138-154 (1975) · Zbl 0277.05139 |
| [7] | Erdős, P.; Gallai, T., On the minimal number of vertices representing the edges of a graph, MTA Mat. Kut. Int. Közl., 6, 181-203 (1961) · Zbl 0101.41001 |
| [8] | Erdős, P.; Hajnal, A.; Moon, J., A problem in graph theory, Amer. Math. Monthly, 71, 1107-1110 (1964) · Zbl 0126.39401 |
| [9] | Grötschel, M.; Lovász, L.; Schrijver, A., Relaxations of vertex packing, J. Combin. Theory Ser. B, 40, 330-343 (1986) · Zbl 0596.05052 |
| [10] | Grötschel, M.; Lovász, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization (1988), Springer: Springer Berlin · Zbl 0634.05001 |
| [11] | Hajnal, A., A theorem on \(k\)-saturated graphs, Canad. J. Math., 17, 720-724 (1965) · Zbl 0129.39901 |
| [12] | König, D., Theorie der endlichen und unendlichen Graphen (1936), Akademische Verlagsgesellschaft: Akademische Verlagsgesellschaft Leipzig · JFM 62.0654.05 |
| [13] | Li, S. R.; Li, W. W., Independence numbers of graphs and generators of ideals, Combinatorica, 1, 55-61 (1981) · Zbl 0524.05037 |
| [14] | Liu, W., Extended formulations and polyhedral projection, (Thesis (1988), Univ. of Waterloo) |
| [15] | Lovász, L., Flats in matroids and geometric graphs, in: Combinatorial Surveys, (Proc. 6th British Comb. Conf. (1977), Academic Press: Academic Press New York), 45-86 · Zbl 0361.05027 |
| [16] | Lovász, L., Some finite basis theorems in graph theory, in: Combinatorics, Coll. Math. Soc. J. Bolyai, Vol. 18, 717-729 (1978) · Zbl 0384.05022 |
| [17] | Lovász, L., On the Shannon capacity of graphs, IEEE Trans. Inform. Theory, 25, 1-7 (1979) · Zbl 0395.94021 |
| [18] | Lovász, L.; Plummer, M. D., Matching Theory (1986), Akadémiai Kiadó: Akadémiai Kiadó Budapest, (North-Holland, Amsterdam) · Zbl 0618.05001 |
| [19] | L. Lovász and A. Schrijver, Matrix cones, projection representations, and stable set polyhedra, in: Polyhedral Combinatorics, DIMACS Series in Discrete Math. and Theor. Comp. Sci. I: 1-17.; L. Lovász and A. Schrijver, Matrix cones, projection representations, and stable set polyhedra, in: Polyhedral Combinatorics, DIMACS Series in Discrete Math. and Theor. Comp. Sci. I: 1-17. · Zbl 0745.05024 |
| [20] | Lovász, L.; Schrijver, A., Cones of matrices and setfunctions, and 0-1 optimization (A. Schrijver), SIAM J. Optim., 1, 166-190 (1990) · Zbl 0754.90039 |
| [21] | Motzkin, T. S.; Strauss, E. G., Maxima for graphs and a new proof of a theorem of Turán, Canad. J. Math., 17, 533-540 (1965) · Zbl 0129.39902 |
| [22] | Sewell, E. C., Stability critical graphs and the stable set polytope, (Res. Report 90-11 (1990), Cornell Comp. Opt. Project) · Zbl 0838.05068 |
| [23] | Sherali, H. D.; Adams, W. P., A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, Siam J. Discrete Math., 3, 411-430 (1990) · Zbl 0712.90050 |
| [24] | Stanley, R. P., Combinatorics and Commutative Algebra (1983), Birkhäuser: Birkhäuser Boston · Zbl 0537.13009 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
