|
2 | added 199 characters in body; added 4 characters in body | ||
|
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 |
||||
|
|
1 |
|
||
Lovasz theta function integralityIs 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.
|
||||
