# Chromatic number of t-perfect graphs

Is every t-perfect graph 4-colourable?

## Remarks

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 [1]. 3-colourability has been proved for some interesting subclasses of t-perfect graphs: claw-free t-perfect graphs by Bruhn and Stein [2], and $P_5$-free t-perfect graphs by Bruhn and Fuchs [3]. The following stronger conjecture was suggested by Sebő: Every triangle-free t-perfect graph is 3-colourable.

Bruhn and Stein [2] also gave a polynomial algorithm for computing an optimal colouring of claw-free h-perfect graphs. Benchetrit [4] 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.

## References

1. A. Schrijver, Combinatorial Optimization - Polyhedra and Efficiency, Section 68.6e
2. H. Bruhn, M. Stein, On claw-free t-perfect graphs, DOI link, author link, supplement
3. H. Bruhn, E. Fuchs, t-perfection in near-bipartite and in $P_5$-free graphs, arXiv link
4. Y. Benchetrit, Integer round-up property for the chromatic number of some h-perfect graphs, arXiv link