Name
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s10107-010-0436-9 | Math. Program. |
Keywords | Field | DocType |
optimal colouring,chromatic number,odd-cycle inequality,claw-free t-perfect graph,stable set polytope,claw-free h-perfect graph,polynomial-time algorithm | Discrete mathematics,Combinatorics,Indifference graph,Chordal graph,Cograph,Pathwidth,1-planar graph,Mathematics,Trapezoid graph,Split graph,Strong perfect graph theorem | Journal |
Volume | Issue | ISSN |
133 | 1-2 | 1436-4646 |
Citations | PageRank | References |
2 | 0.37 | 17 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| henning bruhn | 1 | 177 | 24.93 |
| maya stein | 2 | 81 | 15.65 |