DeLaVina-Pepper lower bound idea

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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s