On the b-Stable Set Polytope of Graphs without Bad K4
On the b-Stable Set Polytope of Graphs without Bad K4
复制标题
关于无坏K4图的b-稳定多面体集
DOI：
10.1137/s0895480102417343
复制
发表时间：
2003
影响因子：
0.8
通讯作者：
A. Schrijver
中科院分区：
文献类型：
--
作者：
D. Gijswijt;A. Schrijver
本文证明了：对于没有坏K4剖分的图G=（V，E），对于$B\in {\bfZ}_{+}^{V\cup E}$，其b-稳定集多面体是由图G的顶点、边和奇圈所确定的约束系统所决定的.我们还证明了该系统是完全对偶积分的。这与t-完美图有关。
We prove that for a graph G=(V,E) without bad K4 subdivision, and for $b\in {\bf Z}_{+}^{V\cup E}$, the b-stable set polytope is determined by the system of constraints determined by the vertices, edges, and odd circuits. We also prove that this system is totally dual integral. This relates to t-perfect graphs.