A min-max relation for stable sets in graphs with no odd-K_ 4

DOI10.1016/0095-8956(89)90032-4MaRDI QIDQ582302zbMATHOpenAlexFDO

Authors A. M. H. Gerards

Publication date 1989

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(89)90032-4

zbMATH Keywords

bipartite graphsstable setsmin-max relationsnode-covers

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Recommendations

• Stability critical graphs and ranks facets of the stable set polytope
• Odd-\(K_{4}\)'s in stability critical graphs
• A min-max relation for \(K_ 3\)-covers in graphs noncontractible to \(K_ 5\backslash e\)
• On the b-Stable Set Polytope of Graphs without Bad K₄
• Odd cycles and matrices with integrality properties

Cites work

• scientific article; zbMATH DE number 3121293 (Why is no real title available?)
• scientific article; zbMATH DE number 3154393 (Why is no real title available?)
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 3718824 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3637616 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3010471 (Why is no real title available?)
• A class of h-perfect graphs
• A generalization of max flow—min cut
• A strongly polynomial minimum cost circulation algorithm
• An orientation theorem for graphs
• Lectures on matroids
• Matrices with the Edmonds-Johnson property
• Maximum-Minimum Sätze über Graphen
• On certain polytopes associated with graphs
• On the stable set polytope of a series-parallel graph
• On total dual integrality
• Paths, Trees, and Flowers
• Planar 3DM is NP-complete
• Polytope des independants d'un graphe série-parallèle
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Transformations which Preserve Perfectness and H-Perfectness of Graphs

Cited in

(14)

• Coloring graphs with no \(\text{odd-}K_4\)
• Odd-\(K_{4}\)'s in stability critical graphs
• Fractional and integral colourings
• A combinatorial column generation algorithm for the maximum stable set problem
• Stable sets of maximal size in Kneser-type graphs
• Polyhedral techniques in combinatorial optimization I: Theory
• On a theorem of Sewell and Trotter
• A simpler proof for the two disjoint odd cycles theorem
• Gear composition and the stable set polytope
• \(t\)-perfection in \(P_5\)-free graphs
• Separation problems for the stable set polytope
• On the feedback vertex set polytope of a series-parallel graph
• On the b-Stable Set Polytope of Graphs without Bad K₄
• Complementation in T-perfect graphs

This page was built for publication: A min-max relation for stable sets in graphs with no odd-\(K_ 4\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q582302)