×

zbMATH — the first resource for mathematics

On certain polytopes associated with graphs. (English) Zbl 0277.05139

MSC:
05C99 Graph theory
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
05C15 Coloring of graphs and hypergraphs
52Bxx Polytopes and polyhedra
90C10 Integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andrásfai, B, On critical graphs, (), 9-19 · Zbl 0182.58001
[2] Berge, C, Sur une conjecture relative au problème des codes optimaux, comm. 13e assemblée générale de l’URSI, Tokyo, (1962)
[3] Berge, C, ()
[4] Chvátal, V, Edmons polytopes and a hierarchy of combinatorial problems, Discrete math., 4, 305-337, (1973) · Zbl 0253.05131
[5] Cook, S.A, The complexity of theorem-proving procedures, (), 151-158 · Zbl 0363.68125
[6] Dirac, G.A, In abstrakten graphen vorhandene vollständige 4-graphen und ihre unterteilungen, Math. nach., 22, 61-85, (1960) · Zbl 0096.17903
[7] Duffin, R.J, Topology of series-parallel networks, J. math. anal. appl., 10, 303-318, (1965) · Zbl 0128.37002
[8] Edmonds, J, Minimum partition of a matroid into independent subsets, J. res. nat. bur. stand. sect. B, 69, 67-72, (1965) · Zbl 0192.09101
[9] Edmonds, J, Maximum matching and a polyhedron with 0,1-vertices, J. res. nat. bur. stand. sect. B, 69, 125-130, (1965) · Zbl 0141.21802
[10] Edmonds, J, Matroids and the greedy algorithm, Math. programming, 1, 127-136, (1971) · Zbl 0253.90027
[11] Fulkerson, D.R, Blocking and anti-blocking pairs of polyhedra, Math. programming, 1, 168-194, (1971) · Zbl 0254.90054
[12] Gomory, R.E; Graves, R.S; Wolfe, P, An algorithm for integer solutions to linear programs, (), (Nov. 1958)
[13] Harary, F, ()
[14] Karp, R.M, Reducibility among combinatorial problems, () · Zbl 0366.68041
[15] Lovász, L, Normal hypergraphs and the perfect graph conjecture, Discrete math., 2, 253-267, (1972) · Zbl 0239.05111
[16] Lovász, L, A characterization of perfect graphs, J. combinatorial theory, 13, 95-98, (1972) · Zbl 0241.05107
[17] {\scG. L. Nemhauser and L. E. Trotter, Jr.}, Properties of vertex packing and independence systems polyhedra, submitted to Math. Programming. · Zbl 0281.90072
[18] Padberg, M.W, On the facial structure of set packing polyhedra, Math. programming, 5, 199-215, (1973) · Zbl 0272.90041
[19] {\scM. W. Padberg}, Perfect zero-one matrices, submitted to Math. Programming. · Zbl 0327.90022
[20] Sabidussi, G, The lexicographic product of graphs, Duke math. J., 28, 573-578, (1961) · Zbl 0115.41102
[21] Trotter, L.E, Solution characteristics and algorithms for the vertex-packing problem, ()
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.