A Class of Graphs Where Alpha=Theta

For any graph, the independence number <= Lovasz theta <= the clique covering number (that’s the “sandwich theorem”). For perfect graphs, the independence number = the clique covering number. So for perfect graphs, the independence number = Lovasz’ theta function.

Simone Severini asked us if we knew any non-perfect class of graphs where the independence number equals Lovasz’ theta. I suspected that Konig-Egervary graphs (KE graphs, with the defining property that the independence number plus the matching number equals the graph’s order) might be such a class. Patrick did some preliminary characterizations confirming this. So then we tried to prove it. It’s true: the main idea is that a maximum matching together with the vertices not saturated by that matching is a clique covering.

A 5-cycle with a pendant coming off of it is an example of a KE graph which is not perfect. So KE graphs are a class of non-perfect graphs where alpha=theta. We wonder what other classes are known.

 

Advertisements

One thought on “A Class of Graphs Where Alpha=Theta

  1. Pingback: Lovasz graphs | The Independence Number Project

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s