New Difficult Graph

Patrick, running the INP code, has now found the next difficult graph J?`FBo{fdb? on 11 vertices. This one has independence number \alpha equal to 4. Lovasz’s \vartheta correctly predicts the independence number, but no lower bound does.

Both the residue and max_odd_minus_odd_horizontal lower bounds give a value of 3; every other lower bound we know is worse. Again, lower bound theory for the independence number is inadequate. We need a lower bound that gives the correct value for this graph. Another possibility is that this “difficulty” can be removed by finding another forbidden subgraph condition, some graph H such that the independence number of H-free graphs can be computed efficiently.

Here’s a drawing of J?`FBo{fdb?. More details can be found at that link. difficult_graph_20130422014157


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your 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