Paul, Patrick and I have decided to let *Lovász graphs* denote the class of graph where alpha=theta, named of course after the great László Lovász.

Earlier we found that this class of graphs includes the KE graphs. Patrick points out that the Lovász graphs are a proper superclass of these graphs. So the Lovász graphs are a generalization of both the class of König-Egerváry graphs as well as the class of perfect graphs. Interestingly, both of these classes contain the bipartite graphs as a subclass.

The Lovász graphs–like the KE graphs–are not a hereditary class. The 5-cycle with a single pendant adjoining one of its vertices is a Lovasz graph (with alpha=theta=3) whereas the 5-cycle (with alpha=2, and theta=sqrt(5)), an induced subgraph, is not a Lovász graph.

We would like to know a characterization of these graphs.

Pingback: Lovasz != the union of the perfect and the KE graphs | The Independence Number Project

This graphs are named quantum noncontextual graph (QNCG) from 2012 or may be, before. See, as example, “Basic logical structures in quantum correlations” Cabello, Danielsen, López-Tarrida y Portillo http://arxiv.org/abs/1211.5825v2. A paper version of this paper has published in PHYSICAL REVIEW A 88, 032104 (2013) Basic exclusivity graphs in quantum correlations. I am Portillo, but I like the name of Lovasz graphs :)

Just a little observation. Take any graph G and let G’ be the graph constructed by attaching a pendant edge to each vertex of G. Then G’ is a Lovasz graph, since the pendant edges form a clique cover and the newly-created vertices form an independent set. The original graph G could be arbitrarily complicated. So Lovasz graphs can be quite “messy”.