Claw-free Graph - Recognition

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. Somewhat more efficiently, but more complicatedly, 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).

Kloks, Kratsch & Müller (2000) observe that in any claw-free graph, each vertex has at most 2√m 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√m × 2√m matrix multiplication, or faster for vertices with even lower degrees. The worst case for this algorithm occurs when Ω(√m) vertices have Ω(√m) neighbors each, and the remaining vertices have few neighbors, so its total time is O(m3.376/2) = O(m1.688).