Chromatic number of t-perfect graphs
The fractional chromatic number of a t-perfect graph is at most 3. Laurent and Seymour showed that the complement of the line graph of a prism is t-perfect but not 3-colourable, see . 3-colourability has been proved for some interesting subclasses of t-perfect graphs: claw-free t-perfect graphs by Bruhn and Stein , and [math]P_5[/math]-free t-perfect graphs by Bruhn and Fuchs . The following stronger conjecture was suggested by Sebő: Every triangle-free t-perfect graph is 3-colourable.
Bruhn and Stein  also gave a polynomial algorithm for computing an optimal colouring of claw-free h-perfect graphs. Benchetrit  showed that the stable set polytope of h-perfect line-graphs and claw-free t-perfect graphs has the integer decomposition property. It is open if this holds for every claw-free h-perfect graph; the above example of Laurent and Seymour shows that it does not hold for every t-perfect graph.
Related open problems
- A. Schrijver, Combinatorial Optimization - Polyhedra and Efficiency, Section 68.6e
- H. Bruhn, M. Stein, On claw-free t-perfect graphs, DOI link, author link, supplement
- H. Bruhn, E. Fuchs, t-perfection in near-bipartite and in [math]P_5[/math]-free graphs, arXiv link
- Y. Benchetrit, Integer round-up property for the chromatic number of some h-perfect graphs, arXiv link