A graph is claw-free iff it does not contain the complete bipartite graph (known as the "claw graph"; illustrated above) as a forbidden induced subgraph.
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. de Bruijn graphs,
8. empty graphs ,
9. Hanoi graphs,
10. ladder rung graphs,
11. rook graphs,
12. line graphs,
13. lollipop graph,
14. path graphs ,
17. triangular graphs, and
18. two-regular graphs.
The numbers of claw-free 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 connected simple graphs on nodes for , 2, ... are 1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, 1728403, ... (OEIS A022562; illustrated above).
Minty (1980) showed that the maximum independent set problem, which is in general NP-complete on an unrestricted graph, can be solved in strongly polynomial time on a claw-free graph. His proof used the algorithm of Edmonds (1965) to find the maximum weighted matching. However, Nakamura and Tamura (2001) showed that this algorithm fails in some special cases and provided modifications to correct this error. The problem of finding the independent set of maximum cardinality in a claw-free graph was solved by Sbihi (1980).