On claw-free t-perfect graphs
On claw-free t-perfect graphs
复制标题
关于无爪 t 完美图
DOI：
10.1007/s10107-010-0436-9
复制
发表时间：
2012
影响因子：
2.7
通讯作者：
M. Stein
中科院分区：
文献类型：
--
作者：
H. Bruhn;M. Stein
如果一个图的稳定集合多胞形是由非负性、边和奇数循环不等式定义的，则该图被称为完美图。我们用禁止未成年人来描述所有无爪完美图的类别，并证明它们是三色的。此外，我们确定了无爪完美图的色数，并给出了多项式时间算法来计算最佳着色。
A graph is calledt-perfect, if its stable set polytope is defined by non-negativity, edge and odd-cycle inequalities. We characterise the class of all claw-freet-perfect graphs by forbiddent-minors, and show that they are 3-colourable. Moreover, we determine the chromatic number of claw-freeh-perfect graphs and give a polynomial-time algorithm to compute an optimal colouring.