After my CanaDAM talk about the difficult graph J?`FBo{fdb?, Nico Van Cleemput made the following interesting observation. First of all, note that one solution of a difficult graph is to find a forbidden subgraph condition that applies to it. For instance, if the graph is claw-free then it is known that the independence number of the graph can be computed efficiently. There are several other similar theorem of this form They apply to **all** graphs. What Nico points out is that, in order to solve a graph G, it is sufficient to find some class C that contains G, and have a forbidden subgraph condition that applies *just to this class. *This could be much easier.

Advertisements

Pingback: Inefficient Bounds can be Efficient in some cases | The Independence Number Project