Chromatic number of t-perfect graphs

From Egres Open
Jump to: navigation, search

Is every t-perfect graph 4-colourable?


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?


  1. A. Schrijver, Combinatorial Optimization - Polyhedra and Efficiency, Section 68.6e
  2. 2.0 2.1 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 [math]P_5[/math]-free graphs, arXiv link
  4. Y. Benchetrit, Integer round-up property for the chromatic number of some h-perfect graphs, arXiv link