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