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