A class of h-perfect graphs |
| |
Authors: | N. Sbihi J.P. Uhry |
| |
Affiliation: | Laboratoire Artemis, Institut IMAG, BP 68, 38402 St. Martin d''Heres, France |
| |
Abstract: | 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 G1 and a graph G2 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 G1 by an a-b chain (the length of which depends on G1). 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). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|