Residue is a good – maybe the best – lower bound for the independence number. But, the data shows, as n gets larger, its success in exactly predicting the independence number decreases.We need more good efficiently computable lower bounds. I’ve asked Grafitti.pc for help!
Here’s the Survey data:
alpha for 6 out of 8 graphs of order 6 were predicted by residue.
alpha for 38 out of 88 graphs of order 7 were predicted by residue.
alpha for 411 out of 2079 graphs of order 8 were predicted by residue.
alpha for 11620 out of 76783 graphs of order 9 were predicted by residue.
alpha for 501793 out of 5005243 graphs of order 10 were predicted by residue.
Patrick’s INP “survey” function currently tests connected graphs with minimum degree at least 3 and maximum degree no more than n-2 (graphs with or are reducible). These are the graphs reported on above.