Lovasz graphs

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.



3 thoughts on “Lovasz graphs

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

  2. 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 :)

  3. 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”.

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