Site best viewed with IE 6.0, Netscape 6.0, or Mozilla 1.4 or better

The Structure of Claw-Free Graphs

Paul Seymour
Princeton University

A graph is "claw-free" if no vertex has three pairwise nonadjacent neighbours. Claw-free graphs generalize line graphs, and a good deal of work has been done on attempting to extend theorems about line graphs to claw-free graphs.

In joint work with Maria Chudnovsky, we can describe completely the connected claw-free graphs with the additional property that every vertex is in a stable set of size three. All such graphs can be built, using natural operations, starting from pieces that belong to a few well-understood basic classes, namely line graphs, circular interval graphs, subgraphs of the icosahedron and of the Schlafli graph, and a few more.

Dynamic menus by