Let v be a vertex of a connected graph G. Let Even be the number of vertices at even distance from v in G. Let EvenH be the number of edges induced by this same set of vertices. Fajtlowicz observed (in Written on the Wall) that this in a lower bound for the independence number. Now take the max over all vertices. It is easy to see, because distances can be computed efficiently, that this invariant can be computed efficiently.
In the case of the last difficult graph, this invariant is 3, the independence number. If we can find an upper bound that gives 3, then we can predict the independence number of this graph.
For more information and results about this invariant, see Michelle Grigsby’s MS thesis.