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 (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 as an internal vertex), then there must be another adjacency between these edges, preventing this tree from being an induced subgraph. This is because, by the pigeonhole principle. 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 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

, 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 matrix multiplication. Therefore, using fast matrix multiplication.

neighbors; for otherwise by Turán's theorem.

More recently, time.

Enumeration

are

1. 1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, ... .

If the graphs are allowed to be disconnected, the numbers of graphs are even larger: they are

1. 1, 2, 4, 10, 26, 85, 302, 1285, 6170, ... .

A technique of allows the number of claw-free cubic graphs to be counted very efficiently, unusually for graph enumeration problems.

Matchings

and, independently, proved that every claw-free connected graph with an even number of vertices has a perfect matching. That is, there exists a set of edges in the graph such that each vertex is an endpoint of exactly one of the matched edges. The special case of this result for line graphs implies that, in any graph with an even number of edges, one can partition the edges into paths of length two. Perfect matchings may be used to provide another characterization of the claw-free graphs: they are exactly the graphs in which every connected induced subgraph of even order has a perfect matching.

leaves the remaining graph connected. Repeatedly removing matched pairs of vertices in this way forms a perfect matching in the given claw-free graph.

may be performed by a single postorder traversal of a breadth first search, in linear time. provide an alternative linear-time algorithm based on depth-first search, as well as efficient parallel algorithms for the same problem.

-edge matching can be extended to a perfect matching.

Independent sets

An independent set in a line graph corresponds to a matching in its underlying graph, a set of edges no two of which share an endpoint. The blossom algorithm of finds a maximum matching in any graph in polynomial time, which is equivalent to computing a maximum independent set in line graphs. This has been independently extended to an algorithm for all claw-free graphs by and .

Both approaches use the observation that in claw-free graphs, no vertex can have more than two neighbors in an independent set, and so the symmetric difference is a non-maximum independent set, it differs from any maximum independent set by even cycles and so called augmenting paths: induced paths with any augmenting path gives a larger independent set, the task thus reduces to searching for augmenting paths until no more can be found, analogously as in algorithms for finding maximum matchings.

Sbihi's algorithm recreates the blossom contraction step of Edmonds' algorithm and adds a similar, but more complicated, clique contraction step. Minty's approach is to transform the problem instance into an auxiliary line graph and use Edmonds' algorithm directly to find the augmenting paths. After a correction by , Minty's result may also be used to solve in polynomial time the more general problem of finding in claw-free graphs an independent set of maximum weight. Generalizations of these results to wider classes of graphs are also known. By showing a novel structure theorem, gave a cubic time algorithm, which also works in the weighted setting.

Coloring, cliques, and domination

A perfect graph is a graph in which the chromatic number and the size of the maximum clique are equal, and in which this equality persists in every induced subgraph. It is now known (the strong perfect graph theorem) that perfect graphs may be characterized as the graphs that do not have as induced subgraphs either an odd cycle or the complement of an odd cycle (a so-called odd hole). However, for many years this remained an unsolved conjecture, only proven for special subclasses of graphs. One of these subclasses was the family of claw-free graphs: it was discovered by several authors that claw-free graphs without odd cycles and odd holes are perfect. Perfect claw-free graphs may be recognized in polynomial time. In a perfect claw-free graph, the neighborhood of any vertex forms the complement of a bipartite graph. It is possible to color perfect claw-free graphs, or to find maximum cliques in them, in polynomial time.

In general, it is NP-hard to find the largest clique in a claw-free graph. It is also NP-hard to find an optimal coloring of the graph, because (via line graphs) this problem generalizes the NP-hard problem of computing the chromatic index of a graph. For the same reason, it is NP-hard to find a coloring that achieves an approximation ratio better than 4/3. However, an approximation ratio of two can be achieved by a greedy coloring algorithm, because the chromatic number of a claw-free graph is greater than half its maximum degree. A generalization of the edge list coloring conjecture states that, for claw-free graphs, the list chromatic number equals the chromatic number; these two numbers can be far apart in other kinds of graphs.

The claw-free graphs are χ-bounded, meaning that every claw-free graph of large chromatic number contains a large clique. More strongly, it follows from Ramsey's theorem that every claw-free graph of large maximum degree contains a large clique, of size roughly proportional to the square root of the degree. For connected claw-free graphs that include at least one three-vertex independent set, a stronger relation between chromatic number and clique size is possible: in these graphs, there exists a clique of size at least half the chromatic number.

Although not every claw-free graph is perfect, claw-free graphs satisfy another property, related to perfection. A graph is called domination perfect if it has a minimum dominating set is a minimum dominating set this process forms an equally small independent dominating set.

Despite this domination perfectness property, it is NP-hard to determine the size of the minimum dominating set in a claw-free graph. However, in contrast to the situation for more general classes of graphs, finding the minimum dominating set or the minimum connected dominating set in a claw-free graph is fixed-parameter tractable: it can be solved in time bounded by a polynomial in the size of the graph multiplied by an exponential function of the dominating set size.

Structure

overview a series of papers in which they prove a structure theory for claw-free graphs, analogous to the graph structure theorem for minor-closed graph families proven by Robertson and Seymour, and to the structure theory for perfect graphs that Chudnovsky, Seymour and their co-authors used to prove the strong perfect graph theorem. The theory is too complex to describe in detail here, but to give a flavor of it, it suffices to outline two of their results. First, for a special subclass of claw-free graphs which they call quasi-line graphs (equivalently, locally co-bipartite graphs), they state that every such graph has one of two forms:

1. A fuzzy circular interval graph, a class of graphs represented geometrically by points and arcs on a circle, generalizing proper circular arc graphs.

2. A graph constructed from a multigraph by replacing each edge by a fuzzy linear interval graph. This generalizes the construction of a line graph, in which every edge of the multigraph is replaced by a vertex. Fuzzy linear interval graphs are constructed in the same way as fuzzy circular interval graphs, but on a line rather than on a circle.

Chudnovsky and Seymour classify arbitrary connected claw-free graphs into one of the following:

1. Six specific subclasses of claw-free graphs. Three of these are line graphs, proper circular arc graphs, and the induced subgraphs of an icosahedron; the other three involve additional definitions.

2. Graphs formed in four simple ways from smaller claw-free graphs.

3. Antiprismatic graphs, a class of dense graphs defined as the claw-free graphs in which every four vertices induce a subgraph with at least two edges.

Much of the work in their structure theory involves a further analysis of antiprismatic graphs. The Schläfli graph, a claw-free strongly regular graph with parameters srg(27,16,10,8), plays an important role in this part of the analysis. This structure theory has led to new advances in polyhedral combinatorics and new bounds on the chromatic number of claw-free graphs, as well as to new fixed-parameter-tractable algorithms for dominating sets in claw-free graphs.

Notes

References

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

• .

External links

• Claw-free graphs, Information System on Graph Class Inclusions