Ryan Pepper’s suggestion, in the previous post, to find the even levels of a fixed vertex v (the vertices at even distance from v) and the lower bounds (with respect to the existing theory) of these, and then to iterate over all the vertices of the graph solves the previous difficult graph HCR`vr]. This gives the improved lower bound of 3 (the previous best was 2) which matches the Lovasz upper bound and, thus, predicts (correctly) that the independence number is 3.

Advertisements