 TOPICS # Claw-Free Graph 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

3. bishop graphs (and their connected components),

4. cocktail party graphs ,

6. cycle graphs,

8. empty graphs ,

9. Hanoi graphs,

11. rook graphs,

12. line graphs,

13. lollipop graph,

14. path graphs ,

17. triangular graphs, and 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).

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 More things to try:

## References

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."

Claw-Free Graph

## Cite this as:

Mugan, Jonathan William and Weisstein, Eric W. "Claw-Free Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Claw-FreeGraph.html