On claw-free t-perfect graphs |
| |
| Authors: | Henning Bruhn Maya Stein |
| |
| Institution: | 1. Université Pierre et Marie Curie, Equipe Combinatoire et Optimisation, case 189, 4 place Jussieu, 75252, Paris Cedex 05, France
2. Centro de Modelamiento Matemático, Universidad de Chile, Blanco Encalada, 2120, Santiago, Chile
|
| |
| Abstract: | A graph is called t-perfect, if its stable set polytope is defined by non-negativity, edge and odd-cycle inequalities. We characterise the class of all claw-free t-perfect graphs by forbidden t-minors, and show that they are 3-colourable. Moreover, we determine the chromatic number of claw-free h-perfect graphs and give a polynomial-time algorithm to compute an optimal colouring. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
