In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.
A claw is another name for the complete bipartite graph K1,3 (that is, a star graph comprising three edges, three leaves, and a central vertex). A claw-free graph is a graph in which no induced subgraph is a claw; i.e., any subset of four vertices has other than only three edges connecting them in this pattern. Equivalently, a claw-free graph is a graph in which the neighborhood of any vertex is the complement of a triangle-free graph.
Claw-free graphs were initially studied as a generalization of line graphs, and gained additional motivation through three key discoveries about them: the fact that all claw-free connected graphs of even order have perfect matchings, the discovery of polynomial time algorithms for finding maximum independent sets in claw-free graphs, and the characterization of claw-free perfect graphs. They are the subject of hundreds of mathematical research papers and several surveys.
Examples
The line graph L(G) of any graph G is claw-free; L(G) has a vertex for every edge of G, and vertices are adjacent in L(G) whenever the corresponding edges share an endpoint in G. A line graph L(G) cannot contain a claw, because if three edges e1, e2, and e3 in G all share endpoints with another edge e4 then by the pigeonhole principle at least two of e1, e2, and e3 must share one of those endpoints with each other. Line graphs may be characterized in terms of nine forbidden subgraphs; the claw is the simplest of these nine graphs. This characterization provided the initial motivation for studying claw-free graphs. The de Bruijn graphs (graphs whose vertices represent n-bit binary strings for some n, and whose edges represent (n − 1)-bit overlaps between two strings) are claw-free. One way to show this is via the construction of the de Bruijn graph for n-bit strings as the line graph of the de Bruijn graph for (n − 1)-bit strings. The complement of any triangle-free graph is claw-free. These graphs include as a special case any complete graph. Proper interval graphs, the interval graphs formed as intersection graphs of families of intervals in which no interval contains another interval, are claw-free, because four properly intersecting intervals cannot intersect in the pattern of a claw. The same is true more generally for proper circular-arc graphs. The Moser spindle, a seven-vertex graph used to provide a lower bound for the chromatic number of the plane, is claw-free. The graphs of several polyhedra and polytopes are claw-free, including the graph of the tetrahedron and more generally of any simplex (a complete graph), the graph of the octahedron and more generally of any cross polytope (isomorphic to the cocktail party graph formed by removing a perfect matching from a complete graph), the graph of the regular icosahedron, and the graph of the 16-cell. The Schläfli graph, a strongly regular graph with 27 vertices, is claw-free.
Recognition
It is straightforward to verify that a given graph with n vertices and m edges is claw-free in time O(n4), by testing each 4-tuple of vertices to determine whether they induce a claw. With more efficiency, and greater complication, one can test whether a graph is claw-free by checking, for each vertex of the graph, that the complement graph of its neighbors does not contain a triangle. A graph contains a triangle if and only if the cube of its adjacency matrix contains a nonzero diagonal element, so finding a triangle may be performed in the same asymptotic time bound as n × n matrix multiplication. Therefore, using the Coppersmith–Winograd algorithm, the total time for this claw-free recognition algorithm would be O(n3.376).
observe that in any claw-free graph, each vertex has at most 2 neighbors; for otherwise by Turán's theorem the neighbors of the vertex would not have enough remaining edges to form the complement of a triangle-free graph. This observation allows the check of each neighborhood in the fast matrix multiplication based algorithm outlined above to be performed in the same asymptotic time bound as 2 × 2 matrix multiplication, or faster for vertices with even lower degrees. The worst case for this algorithm occurs when Ω() vertices have Ω() neighbors each, and the remaining vertices have few neighbors, so its total time is O(m3.376/2) = O(m1.688).