Claw-free graph

(that is, a star graph comprising three edges, three leaves, and a central vertex).

[7] Therefore, using fast matrix multiplication, the total time for this claw-free recognition algorithm would be

Kloks, Kratsch & Müller (2000) observe that in any claw-free graph, each vertex has at most

This observation allows the check of each neighborhood in the fast matrix multiplication based algorithm outlined above to be performed in the same asymptotic time bound as

vertices grows at least as quickly as the number of triangle-free graphs, exponentially in the square of

Sumner (1974) and, independently, Las Vergnas (1975) proved that every claw-free connected graph with an even number of vertices has a perfect matching.

[8] Sumner's proof shows, more strongly, that in any connected claw-free graph one can find a pair of adjacent vertices the removal of which leaves the remaining graph connected.

may be performed by a single postorder traversal of a breadth first search tree of the graph, rooted at

Faudree, Flandrin & Ryjáček (1997) list several related results, including the following:

The blossom algorithm of Edmonds (1965) 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 Sbihi (1980) and Minty (1980).

[9] 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.

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

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 Nakamura & Tamura 2001, 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.

[9] By showing a novel structure theorem, Faenza, Oriolo & Stauffer (2011) gave a cubic time algorithm, which also works in the weighted setting.

[10] However, for many years this remained an unsolved conjecture, only proven for special subclasses of graphs.

It is possible to color perfect claw-free graphs, or to find maximum cliques in them, in polynomial time.

[11] In general, it is NP-hard to find the largest clique in a claw-free graph.

[6] For the same reason, it is NP-hard to find a coloring that achieves an approximation ratio better than 4/3.

However, an approximation ratio of two can be achieved by a greedy coloring algorithm, because the chromatic number of a claw-free graph is greater than half its maximum degree.

More strongly, it follows from Ramsey's theorem that every claw-free graph of large maximum degree contains a large clique, of size roughly proportional to the square root of the degree.

For connected claw-free graphs that include at least one three-vertex independent set, a stronger relation between chromatic number and clique size is possible: in these graphs, there exists a clique of size at least half the chromatic number.

can be replaced by one of the undominated vertices in its clique producing a dominating set with fewer adjacencies.

By repeating this replacement process one eventually reaches a dominating set no larger than

[6] However, in contrast to the situation for more general classes of graphs, finding the minimum dominating set or the minimum connected dominating set in a claw-free graph is fixed-parameter tractable: it can be solved in time bounded by a polynomial in the size of the graph multiplied by an exponential function of the dominating set size.

[10] The theory is too complex to describe in detail here, but to give a flavor of it, it suffices to outline two of their results.

This structure theory has led to new advances in polyhedral combinatorics and new bounds on the chromatic number of claw-free graphs,[5][17] as well as to new fixed-parameter-tractable algorithms for dominating sets in claw-free graphs.