8
$\begingroup$

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.

     (source)

Its true for a few other non-perfect graphs I tried, here's a Mathematica package I used to compute it

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

No. For some examples see When the Lovász theta-function saturates its upper bound

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .