# 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 [math]P_5[/math]-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.

## Related open problems

Are t-perfect graphs strongly t-perfect?

## References

- ↑ A. Schrijver,
*Combinatorial Optimization - Polyhedra and Efficiency*, Section 68.6e - ↑
^{2.0}^{2.1}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