A claw-free graph is a simple graph that contains no induced subgraph isomorphic
to the complete bipartite graph , known as the "claw
graph" (illustrated above).
The line graph of any graph is claw-free, as is the complement of any triangle-free graph.
Classes of graphs that are claw-free include
1. antiprism graphs,
2. barbell graphs,
3. bishop graphs (and their connected components),
5. complete graphs,
6. cycle graphs,
7. empty graphs ,
8. Hanoi graphs,
10. rook graphs,
11. line graphs,
12. lollipop graphs,
13. path graphs ,
15. triangular graphs, and
16. two-regular graphs.
The numbers of claw-free unlabeled simple graphs on nodes for
, 2, ... are 1, 2, 4, 10, 26,
85, 302, 1285, 6170, ... (OEIS A086991; illustrated
above).
The numbers of claw-free unlabeled connected simple graphs on nodes for
, 2, ... are 1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389,
184749, 1728404, ... (OEIS A022562; illustrated
above).
The maximum independent set problem, which is NP-hard on unrestricted simple graphs, can be solved in polynomial time on claw-free graphs. Minty (1980) gave an algorithm based on the maximum-weight matching algorithm of Edmonds (1965a). Nakamura and Tamura (2001, pp. 194-195 and 201) showed that Minty's weighted version fails in some cases and corrected it. The unweighted version is unaffected. Sbihi (1980) also gave an algorithm for finding an independent vertex set of maximum cardinality in a claw-free graph.
Mishra et al. (2026, Theorem 1.1) proved that every finite claw-free perfect graph satisfies
where
is the choice number,
is the chromatic number,
and
is the clique number. The perfect
graph hypothesis is essential to the scope of this result.