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.

Pingback: Lovasz graphs | The Independence Number Project