Lovasz != the union of the perfect and the KE graphs

The Lovász graphs (graph where alpha=theta) include the perfect graphs as well as the König-Egerváry (KE) graphs. Paul asked for an example of a Lovász graph which was neither perfect nor KE.

So Patrick found the following example. Its g6 string is “FCQbo”. Its independence number is 3, matching number is 3, but its order is 7. Theta is 3. It is not perfect as it has an odd hole.

FCQbo

Advertisements

One thought on “Lovasz != the union of the perfect and the KE graphs

  1. It should be noticed that twin vertices reduction is not only an α-reduction but a θ-reduction. Thus we can reduce vertices 1 and 4, where the resulting graph is KE, and find out that α=θ in the original graph.

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