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: