Polyhedral characterizations and perfection of line graphs

DOI10.1016/S0166-218X(97)00081-4zbMath0903.05041MaRDI QIDQ1382259

Dasong Cao, Nemhauser, George I.

Publication date: 10 December 1998

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

stable setline graphperfect\(h\)-perfect\(t\)-perfect

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Related Items (5)

Integer round-up property for the chromatic number of some \(h\)-perfect graphs ⋮ Toric rings of perfectly matchable subgraph polytopes ⋮ On claw-free \(t\)-perfect graphs ⋮ Clique family inequalities for the stable set polytope of quasi-line graphs. ⋮ A note on kernels and Sperner's Lemma

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching theory
• Geometric algorithms and combinatorial optimization
• On graphs whose least eigenvalue exceeds \(-1-\sqrt2\)
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Graphe représentatif des arêtes d'un multigraphe
• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• Line perfect graphs
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: Polyhedral characterizations and perfection of line graphs