Patrick, running the INP code, has now found the next difficult graph J?`FBo{fdb? on 11 vertices. This one has independence number equal to 4. Lovasz’s 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.