Claw-Free Graph


A graph is claw-free iff it does not contain the complete bipartite graph K_(1,3) (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),

4. cocktail party graphs K_(n×2),

5. complete graphs,

6. cycle graphs,

7. de Bruijn graphs,

8. empty graphs K^__n,

9. Hanoi graphs,

10. ladder rung graphs,

11. rook graphs,

12. line graphs,

13. lollipop graph,

14. path graphs P_n,

15. Sierpiński gasket graphs,

16. strongly perfect graphs,

17. triangular graphs, and

18. two-regular graphs.


The numbers of claw-free simple graphs on n nodes for n=1, 2, ... are 1, 2, 4, 10, 26, 85, 302, 1285, 6170, ... (OEIS A086991; illustrated above).


The numbers of claw-free connected simple graphs on n nodes for n=1, 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).

See also

Claw Graph, Complete Bipartite Graph, Forbidden Induced Subgraph, Line Graph, Perfect Matching

Portions of this entry contributed by Jonathan William Mugan

Explore with Wolfram|Alpha


Edmonds, J. "Paths, Trees, and Flowers." Canad. J. Math. 17, 449-467, 1965.Faudree, R.; Flandrin, E.; and Ryjáček, Z. "Claw-Free Graphs--A Survey." Disc. Math. 164, 87-147, 1997.Minty, G. J. "On Maximal Independent Sets of Vertices in Claw Free Graphs." J. Combin. Th. B 28, 284-304, 1980.Nakamura, D. and Tamura, A. "A Revision of Minty's Algorithm for Finding a Maximum Weight Stable Set of a Claw-Free Graph." J. Oper. Res. Soc. Japan 44, 194-204, 2001.Sbihi, N. "Algorithme de Recherche d'un Stable de Cardinalite Maximum dans un Graphe sans Étoile." Disc. Math. 29, 53-76, 1980.Sloane, N. J. A. Sequences A022562 and A086991 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Claw-Free Graph

Cite this as:

Mugan, Jonathan William and Weisstein, Eric W. "Claw-Free Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications