graphs of odd order with at most one degree-one vertex may be partitioned into an odd cycle and a matching; for any k that is at most half the minimum degree of a claw-free graph in which either k or the number of vertices is even, the graph has a k-factor; and, if a claw-free graph is (2k + 1)-connected, then any k-edge matching can be extended to a perfect matching. Independent sets An independent set in a line graph corresponds to a matching in its underlying graph, a set of edges no two of which share an endpoint. The blossom algorithm of finds a maximum matching in any graph in polynomial time, which is equivalent to computing a maximum independent set in line graphs. This has been independently extended to an algorithm for all claw-free graphs by and . Both approaches use the observation that in claw-free graphs, no vertex can have more than two neighbors in an independent set, and so the symmetric difference of two independent sets must induce a subgraph of degree at most two; that is, it is a union of paths and cycles. In particular, if I is a non-maximum independent set, it differs from any maximum independent set by even cycles and so called augmenting paths: induced paths which alternate between vertices not in I and vertices in I, and for which both endpoints have only one neighbor in I. As the symmetric difference of I with any augmenting path gives a larger independent set, the task thus reduces to searching for augmenting paths until no more can be found, analogously as in algorithms for finding maximum matchings. Sbihi's algorithm recreates the blossom contraction step of Edmonds' algorithm and adds a similar, but more complicated, clique contraction step. Minty's approach is to transform the problem instance into an auxiliary line graph and use Edmonds' algorithm directly to find the augmenting paths. After a correction by , Minty's result may also be used to solve in polynomial time the more general problem of finding in claw-free graphs an independent set of maximum weight. Generalizations of these results to wider classes of graphs are also known. By showing a novel structure theorem, gave a cubic time algorithm, which also works in the weighted setting. Coloring, cliques, and domination A perfect graph is a graph in which the chromatic number and the size of the maximum