I plan to take a fresh look at the lower bound theory for the independence number. If a graph has a pendant vertex then that pendant can always be included in a maximum independent set. Critical independent sets are a generalization of this notion. And they can be efficiently identified and included in a maximum independent set. So we restrict our attention to graphs with empty critical independent sets (so ).

Residue is the best lower bound I have tested. This summer Jochen Harant told me of a bound I have not yet programmed but will do this very soon. Here is the new data:

Advertisements