A class of h-perfect graphs

DOI10.1016/0012-365X(84)90071-2MaRDI QIDQ799701zbMATH OpenOpenAlexFDO

Authors Najiba Sbihi, Jean-Pierre Uhry

Publication date 1984

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(84)90071-2

zbMATH Keywords

h-perfectindependent setsSeries-parallel graphs

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph theory (05C99)

Review text

The summary of the authors: A graph is said to be h-perfect if the convex hull of its independent sets is defined by the constraints corresponding to cliques and odd holes, and the nonnegativity constraints. Series-parallel graphs and perfect graphs are h-perfect. The purpose of this paper is to extend the class of graphs known to be h- perfect. Thus, given a graph which is the union of a bipartite graph \(G_ 1\) and a graph \(G_ 2\) having exactly two common nodes a and b, and no edge in common, we prove that G is h-perfect if so is the graph obtained from G by replacing \(G_ 1\) by an a-b chain (the length of which depends on \(G_ 1)\). This result enables us to prove that the graph obtained by substituting bipartite graphs for edges of a series- parallel graph is h-perfect, and also that the identification of two nodes of a bipartite graph yields an h-perfect graph (modulo a reduction which preserves h-perfection).

Recommendations

• Two classes of perfect graphs
• Progress on perfect graphs
• Stable set bonding in perfect graphs and parity graphs
• New classes of perfect graphs
• scientific article; zbMATH DE number 3887730

Cites work

• Blocking and anti-blocking pairs of polyhedra
• Maximal Flow Through a Network
• Polytope des independants d'un graphe série-parallèle
• Transformations which Preserve Perfectness and H-Perfectness of Graphs

Cited in

(11)

• Matrices with the Edmonds-Johnson property
• On the stable set polytope of a series-parallel graph
• On cutting-plane proofs in combinatorial optimization
• Claw-free t-perfect graphs can be recognized in polynomial time
• Characterising claw-free t-perfect graphs
• scientific article; zbMATH DE number 4031747 (Why is no real title available?)
• On claw-free t-perfect graphs
• On the Gorenstein property of the Ehrhart ring of the stable set polytope of an h-perfect graph
• A min-max relation for stable sets in graphs with no odd-\(K_ 4\)
• Codegree and regularity of stable set polytopes
• A note on kernels and Sperner's Lemma

This page was built for publication: A class of h-perfect graphs

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