*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.

2/9/04

*Dynamic menus by **
*