Nico also points out that bounds which aren’t efficiently computable in general can be computed efficiently in special cases. For instance, the chromatic number is not generally efficiently computable – but is for bipartite graphs, perfect graphs, etc.

In the case of the difficult graph J?`FBo{fdb?, the chromatic number is 3. Since (independence number)(chromatic number) is always at least the order of the graph, since the order is 11, and independence number is integral, this implies that independence number is at least 4, which exactly predicts its true value.

So… maybe graph J?`FBo{fdb? belongs to some class of graphs where chromatic number can be computed efficiently? This would solve our problem.

Advertisements