Enumeration
Because claw-free graphs include complements of triangle-free graphs, the number of claw-free graphs on n vertices grows at least as quickly as the number of triangle-free graphs, exponentially in the square of n. The numbers of connected claw-free graphs on n nodes, for n = 1, 2, ... are
- 1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, ... (sequence A022562 in OEIS).
If the graphs are allowed to be disconnected, the numbers of graphs are even larger: they are
- 1, 2, 4, 10, 26, 85, 302, 1285, 6170, ... (sequence A086991 in OEIS).
A technique of Palmer, Read & Robinson (2002) allows the number of claw-free cubic graphs to be counted very efficiently, unusually for graph enumeration problems.
Read more about this topic: Claw-free Graph