# T-perfect and h-perfect graphs

## t-perfect and 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.

A motivation for defining t-perfectness is that the third condition can be checked in polynomial time. Eisenbrand et al. ^{[1]} gave a combinatorial, polynomial-time algorithm for finding a maximum weight stable set in a t-perfect graph.
For a detailed description, see Chapter 68 of Schrijver's book ^{[2]}. Polynomial-time recognition of t-perfect graphs is open, but it is solved for claw-free t-perfect graphs ^{[3]}.

## h-perfect graphs

A graph *G=(V, E)* is **h-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(Q) & \leq 1 & \text{ for each clique } Q,\\ x(V(C)) & \leq \lfloor |V(C)|/2 \rfloor & \text{ for each odd circuit } C. \end{array} [/math]

The class of h-perfect graphs was introduced by Sbihi and Uhry ^{[4]}; it is a superclass of perfect and t-perfect graphs. The maximum weight stable set can be found in polynomial time in h-perfect graphs using semidefinite programming ^{[5]}; however, no combinatorial algorithm is known.

## References

- ↑ F. Eisenbrand, S. Funke, N. Garg, J. Könemann,
*A combinatorial algorithm for computing a maximum independent set in a t-perfect graph*, ACM link, author link - ↑ A. Schrijver,
*Combinatorial Optimization - Polyhedra and Efficiency*, Springer, google books link - ↑ H. Bruhn, O. Schaudt,
*Claw-free t-perfect graphs can be recognised in polynomial time*, DOI link, author link - ↑ N. Sbihi, J.P. Uhry,
*A class of h-perfect graphs*, DOI link - ↑ L. Lovász, A. Schrijver,
*Cones of matrices and setfunctions, and 0-1 optimization*, DOI link, author link