Welcome to MathOverflow

Question

7

1

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.

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

edited Mar 4 2011 at 19:24

asked Mar 4 2011 at 10:28

Yaroslav Bulatov
1,110●4●17

Chris Godsil · Accepted Answer · 2011-03-05 11:29:19Z UTC

4

No. For some examples see http://mathoverflow.net/questions/46534/when-the-lovasz-theta-function-saturates-its-upper-bound

answered Mar 5 2011 at 11:29

Chris Godsil
5,674●1●8●22

Lovasz theta function integrality

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.