University of Ghent talk slides and comments

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:

  1. 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.
  2. 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?
  3. 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.

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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