Are t-perfect graphs strongly t-perfect?
From Egres Open
(Redirected from Strongly t-perfect graphs)
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?
Remarks
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.
References
- ↑ A. M. Gerards, A min-max relation for stable sets in graphs with no odd-K4, DOI link
- ↑ A. Schrijver, Strong t-perfection of bad-K4-free graphs, DOI link, Author link.
- ↑ H. Bruhn, M. Stein, t-perfection is always strong for claw-free graphs, DOI link, author link
