# Need tight lower bound for independence number of order 10 graph

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.

-
How did you get 3? I can't even do better than 2 :( –  Felix Goldberg Jan 25 '13 at 22:09
Probably it won't fly, but the approach is worth looking at: tu-ilmenau.de/fileadmin/media/math/Preprints/2009/… –  Felix Goldberg Jan 25 '13 at 22:19
Try numerical order. I found such a set of 4 independent points. For such graphs, I find using the triangles helps. Gerhard "Ask Me About System Design" Paseman, 2013.01.25 –  Gerhard Paseman Jan 26 '13 at 0:49
@AnthonyQuas: I think the OP is asking for a "principled" derivation of the fact that $\alpha=4$, not just for the calculation. It's a very interesting project... –  Felix Goldberg Jan 26 '13 at 1:05
Towards your goal of furthering new theory, you might present ten such minimal graphs and ask what else they may have in common; that might spur the development of new and better lower bounds. Gerhard "Ask Me About System Design" Paseman, 2013.01.25 –  Gerhard Paseman Jan 26 '13 at 1:52

A simple method will be to run a greedy algorithm for finding an independent set: recursively choose a vertex of the least degree (and least index), add it to the set, and remove it and all its neighbors from the graph.

I'm not sure if that's what you mean by a method, but it works for the mentioned example.

-
Nice! I used to think that this procedure produces the Caro-Wei bound, which I checked straight away and got only 2. Turns out that its stronger - this paper (pirate.shu.edu/~kahlnath/indnum.pdf) attributes the procedure and the resultant bound to Murphy (section 3). –  Felix Goldberg Jan 26 '13 at 0:21
It only works here if you happen to pick the right vertex of lowest degree to start with -- if you start by picking $5$, you'll only end up with a set of size $3$. –  Kevin P. Costello Jan 26 '13 at 1:02