Skip to main content
Copied image to imgur.com, as it was not being displayed because of the new https rule. Added link to original image source.
Source Link

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

     (source)

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

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

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

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

added 199 characters in body; added 4 characters in body
Source Link

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

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

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

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

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

Source Link

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