Are t-perfect graphs strongly t-perfect?

From Egres Open
Jump to: navigation, search

A graph G=(V, E) is t-perfect if its stable set polytope is determined by the system

[math]\begin{array}{rll} x(v) & \geq 0 & \text{ for each } v \in V,\\ x(u) + x(v) & \leq 1 & \text{ for each } uv \in E,\\ x(V(C)) & \leq \lfloor |V(C)|/2 \rfloor & \text{ for each odd circuit } C. \end{array} [/math]

A graph is strongly t-perfect if the above system is TDI.

Is it true that every t-perfect graph is strongly t-perfect?


Gerards [1] proved that a graph without an odd [math]K_4[/math]-subdivision is strongly t-perfect. This has been generalized by Schrijver [2] to all graphs without a bad subdivision of K4 (a subdivision of K4 is bad if it is not t-perfect).

Bruhn and Stein [3] proved that claw-free t-perfect graphs are strongly t-perfect.


  1. A. M. Gerards, A min-max relation for stable sets in graphs with no odd-K4, DOI link
  2. A. Schrijver, Strong t-perfection of bad-K4-free graphs, DOI link, Author link.
  3. H. Bruhn, M. Stein, t-perfection is always strong for claw-free graphs, DOI link, author link