HCrb‘rc solved + Newest Difficult graph

For the graph HCrb‘rc, the best upper bound (Lovasz’s theta) implied that the independence number to be no more than 3, while the best lower bound (a tie between radius, residue, and max even minus even horizontal) forced the independence number was at least 2. So there is a gap – the theory implemented into INP doesn’t imply that the independence number can be predicted.

is 3.So Patrick looked for a bound that wasn’t yet implemented in INP that would make an improved prediction. he found Seklow’s improvement of the Caro-Wei lower bound for the independence number. It is efficiently computable and predicts that the independence number of HCrb‘rc is at least 3. So efficiently computable independence number theory yield that the independence number of HCrb‘rc.

After adding Seklow’s bound to the program, Patrick generated the next difficult graph HCrb‘rk, pictured below:


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