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
