Polyhedral characterizations and perfection of line graphs

DOI10.1016/S0166-218X(97)00081-4MaRDI QIDQ1382259zbMATH OpenFDO

Authors Dasong Cao, G. L. Nemhauser

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

line graphstable setperfect\(h\)-perfect\(t\)-perfect

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Cites work

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

Cited in

(7)

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

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

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