Ryan Pepper and Ermelinda DeLaVina just sent me the following idea for lower bounds, which can be generalized.

Consider the lower bound L described as follows. Let M denote the set of vertices of maximum degree. If [V-M] is bipartite, then its independence number can be computed efficiently and L=alpha[V-M]. Otherwise, L=1.

Since it can be also efficiently checked if a graph is bipartite or not, and it is a simple thing to remove max degree vertices, L is an efficiently computable lower bound for alpha.

Moreover, for the latest difficult graph J?`FBo{fdb?, the deletion of the four max degree vertices 7,8,9,10 will leave a forest whose independence can be efficiently computed.

Advertisements