On stable set polyhedra for K1,3-free graphs

Journal of Combinatorial Theory, Series B - Tập 31 - Trang 313-326 - 1981
Rick Giles1,2
1Department of Mathematics, University of Kentucky, USA
2Institut für Ökonometrie und Operations Research, Universität Bonn, West Germany

Tài liệu tham khảo

Berge, 1973 Bland, 1979, Graphical properties related to minimal imperfection, Discrete Math., 27, 11, 10.1016/0012-365X(79)90065-7 Chvátal, 1973, Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Math., 4, 305, 10.1016/0012-365X(73)90167-2 Chvátal, 1976, On the strong perfect graph conjecture, J. Combin. Theory Ser. B, 20, 139, 10.1016/0095-8956(76)90005-8 Edmonds, 1965, Maximum matching and a polyhedron with 0,1-vertices, J. Res. Nat. Bur. Standards Sect. B, 69, 125, 10.6028/jres.069B.013 Edmonds, 1970, Submodular functions, matroids, and certain polyhedra, 69 Fulkerson, 1972, Anti-blocking polyhedra, J. Combin. Theory Ser. B, 12, 50, 10.1016/0095-8956(72)90032-9 Fulkerson, 1973, On the perfect graph theorem, 69 F. R. Giles, L. E. Trotter, Jr., and A. C. Tucker, The strong perfect graph theorem for a class of partitionable graphs, in “Perfect Graphs” (C. Berge and V. Chvátal, Eds.), in press. W.-L. Hsu and G. L. Nemhauser, Algorithms for minimum covering by cliques and maximum clique in claw-free perfect graphs, Discrete Math., in press. Koch, 1979, Ramifications of Matching Theory Lovász, 1972, Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2, 253, 10.1016/0012-365X(72)90006-4 Lovász, 1972, A characterization of perfect graphs, J. Combin. Theory Ser. B, 13, 95, 10.1016/0095-8956(72)90045-7 Minty, 1980, On maximal independent sets of vertices in claw-free graphs, J. Combin. Theory Ser. B, 21, 212 Nemhauser, 1974, Properties of vertex packing and independence system polyhedra, Math. Programming, 6, 48, 10.1007/BF01580222 Padberg, 1973, On the facial structure of set-packing polyhedra, Math. Programming, 5, 199, 10.1007/BF01580121 Padberg, 1974, Perfect zero-one matrices, Math. Programming, 6, 180, 10.1007/BF01580235 Padberg, 1976, Almost integral polyhedra related to certain combinatorial optimization problems, Linear Algebra Appl., 15, 69, 10.1016/0024-3795(76)90079-3 Parthasarathy, 1976, The strong perfect-graph conjecture is true for K1,3-free graphs, J. Combin. Theory Ser. B, 21, 212, 10.1016/S0095-8956(76)80005-6 Sbihi, 1978, Étude des Stables dans les Graphes sans Étoile Trotter, 1975, A class of facet producing graphs for vertex packing polyhedra, Discrete Math., 12, 373, 10.1016/0012-365X(75)90077-1 Tucker, 1975, Coloring a family of circular arcs, SIAM J. Appl. Math., 29, 493, 10.1137/0129040 Tucker, 1977, Critical perfect graphs and perfect 3-chromatic graphs, J. Combin. Theory Ser. B, 23, 143, 10.1016/0095-8956(77)90064-8 Tucker, 1979, Berge's strong perfect graph conjecture, Ann. N. Y. Acad. Sci., 319, 530, 10.1111/j.1749-6632.1979.tb32832.x Zemel, 1974