The other day I mentioned our interest in characterizing graphs where the independence number and Lovasz’s theta function were equal to Ed Scheinerman . So this would be a class of graphs which includes the perfect graphs. He suggested that we try to characterize the graphs where the independence number equals Lovasz’s theta for *all * induced subgraphs. At first this sounded absurd to me – it would be hard enough doing this for the graph itself much less adding the condition of *all* subgraphs.

Of course the class of graphs that Scheinermman mentions sits *between* the class of perfect graphs and the class of graphs where the independence number equals Lovasz’s theta. Its a more restrictive class – there’s more structure. This may give us something to get going with. It’s a great idea.

# Scheinerman’s Idea

Advertisements

Unfortunately, I don’t think you get anything in addition to the perfect graphs themselves. Indeed, if a graph is not perfect, then it contains an odd hole or odd antihole as an induced subgraph. For odd holes and odd antiholes, the Lovasz number is greater than the stability number.