Strong T-Perfection of Bad-K4-Free Graphs
Strong T-Perfection of Bad-K4-Free Graphs
复制标题
无 Bad-K4 图的强 T 完美
DOI：
10.1137/s0895480101401101
复制
发表时间：
2002
影响因子：
0.8
通讯作者：
A. Schrijver
中科院分区：
文献类型：
--
作者：
A. Schrijver
我们证明了每个图不包含一个坏的细分-K4作为一个子图是强t-完美的。这里一个图G=（V，E）是强t-完美的，如果对于每个权函数$w：V\to\mathbb{Z}_+$，一个稳定集的最大权等于覆盖任意顶点v至少w（v）次的顶点、边和圈族的最小（总）代价。根据定义，顶点或边的成本为1，回路C的成本为$\lfloor\frac{1}{2}| VC|\rfloor$. K4的细分称为坏的，如果每个三角形已成为一个奇回路，如果它不是通过使K4的4-回路中的边缘获得的。均匀细分，而其他两个边不细分。
该定理推广了Gerards [J. Combin. Theory Ser. B，47（1989），pp. 330- 348]关于奇-K4-自由图的强t-完全性和Gerards和Shepherd [SIAM J.离散数学，11（1998），pp. 524- 545]关于无坏K4图的t-完美性。
We show that each graph not containing a bad subdivision of -K4 as a subgraph is strongly t-perfect. Here a graph G=(V,E) is strongly t-perfect if, for each weight function $w:V\to\mathbb{Z}_+$, the maximum weight of a stable set is equal to the minimum (total) cost of a family of vertices, edges, and circuits covering any vertex v at least w(v) times. By definition, the cost of a vertex or edge is 1, and the cost of a circuit C is $\lfloor\frac{1}{2}|VC|\rfloor$. A subdivision of K4 is called bad if each triangle has become an odd circuit and if it is not obtained by making the edges in a 4-circuit of K4. evenly subdivided, while the other two edges are not subdivided.
The theorem generalizes earlier results of Gerards [J. Combin. Theory Ser. B, 47 (1989), pp. 330--348] on the strong t-perfection of odd-K4-free graphs and of Gerards and Shepherd [SIAM J. Discrete Math., 11 (1998), pp. 524--545] on the t-perfection of bad-K4-free graphs.