A class of h-perfect graphs
A class of h-perfect graphs
复制标题
一类 h 完美图
DOI：
10.1016/0012-365x(84)90071-2
复制
发表时间：
1984
影响因子：
0.8
通讯作者：
J. Uhry
中科院分区：
文献类型：
--
作者：
N. Sbihi;J. Uhry
一个图称为-完美图，如果它的独立集的凸船体是由对应于团和奇洞的约束和非负约束定义的。串平行图和完美图是h-完美图。本文的目的是推广已知的beh-完美图类。因此，给定一个图，它是一个二分图G1和一个图G2的并，其中恰好有两个公共结点a和b，并且没有公共边，我们证明了Gish-完美的，如果是这样的图，通过用一个-b链（它的长度取决于G1）将G1包围而从G得到。这一结果使我们能够证明用二部图代替串-平行图的边所得到的图是-完美的，并且证明了二部图的两个节点的识别产生了-完美图（模约简是-完美的）.
A graph is said to beh-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 areh-perfect. The purpose of this paper is to extend the class of graphs known to beh-perfect. Thus, given a graph which is the union of a bipartite graphG1and a graphG2having exactly two common nodesaandb, and no edge in common, we prove thatGish-perfect if so is the graph obtained fromGby replacingG1by ana-bchain (the length of which depends onG1). This result enables us to prove that the graph obtained by substituting bipartite graphs for edges of a series-parallel graph ish-perfect, and also that the identification of two nodes of a bipartite graph yields anh-perfect graph (modulo a reduction which preservesh-perfection).