Here’s the slides of the talk I gave (“Problems and Results Motivated by Efficient
Computation of the Independence Number”) two Fridays ago at the University of Ghent. Among the comments were:
- that it would be useful to have more than one difficult graph at a time – maybe its possible that, with several graphs, a pattern can be seen.
- there was a discussion about the “goodness” of a bound for the independence number. I used “good” in the sense that the percentage of graphs for which equality of the bound and independence number hold is high. Another possible measure is the ration of the independence number with the bound. How large can this ratio be?
- that computing the automorphism group of the graph could be useful. If the automorphism group isn’t trivial then it may be possible to get something – including better/different visualizations using that structure.
We plan on addressing the first and third. The residue of a graph, which is a lower bound for the independence number, was discussed in the talk, and generated some interest. The class of graphs for which equality holds, for instance, is not known.