Skip to main content
1 of 3

Lovasz theta function integrality

Is anything known about Lovasz Theta Function taking integral value in non-perfect graphs? In particular, does integral value of Lovasz theta always coincide with the size of largest independent set?

For instance, graph below is non-perfect, and its Lovasz theta function gives the independence number.

http://yaroslavvb.com/upload/save/non-perfect.png