On maximal independent sets of vertices in claw-free graphs

AbstractA graph is claw-free if: whenever three (distinct) vertices are joined to a single vertex, those three vertices are a nonindependent (nonstable) set. Given a finite claw-free graph with real numbers (weights) assigned to the vertices, we exhibit an algorithm for producing an independent set of vertices of maximum total weight. This algorithm is “efficient” in the sense of J. Edmonds, that is to say, the number of computational steps required is of polynomial (not exponential or factorial) order in n, the number of vertices of the graph. This problem was solved earlier by Edmonds for the special case of “edge-graphs”; our solution is by reducing the more general problem to the earlier-solved special case. Separate attention is given to the case in which all weights are (+1) and thus an independent set is sought which is maximal in the sense of its cardinality