The independence number of a graph is the cardinality of a maximum set of vertices which are pairwise non-adjacent. It is an NP-hard graph invariant.
There are a variety of ways to efficiently reduce the calculation of the independence number, for instance, if the graph has a simplicial vertex, there is a maximum independent set which contains it (these can be identified efficiently and then it and its neighbors can be removed). There are a variety of graph classes, for instance, claw-free graphs, where it is known that the independence number can be computed efficiently. There are a variety of efficiently computable upper and lower bounds for the independence number of a graph including, respectively, Lovasz's theta function and the residue.
The graph I?bbrr[ko (in B. McKays Graph-6 notation, picture below) has independence number 4. It is the smallest graph such that, using the theory of the independence number of a graph, can not be efficiently reduced, nor belongs to a class where the independence number can be efficiently computed, nor whose value can be predicted from known efficiently computable upper and lower bounds.
In this case, I know the independence number is 4. Lovasz's theta function upper bound gives the exact value of the independence number - but no lower bound that I know of gives the correct value of 4 - no lower bound that I am aware of gives a better value than 3. Would anyone know a lower bound for the independence number of a graph that gives the value 4 for graph I?bbrr[ko ?
I am trying to see how far the existing theory for the efficient computation of the independence number of a graph can be taken - and then find examples that will motivate new theory.
A drawing of the graph can be found here.