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.

Advertisements

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.