Scheinerman’s Idea

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.

Advertisements

One thought on “Scheinerman’s Idea

  1. 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.

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