Claw-free Graph - Examples

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 e₁, e₂, and e₃ in G all share endpoints with another edge e₄ then by the pigeonhole principle at least two of e₁, e₂, and e₃ 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 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.