7 - The structure of claw-free graphs  pp. 153-172

By Maria Chudnovsky and Paul Seymour

Image View

Abstract

A graph is claw-free if no vertex has three pairwise nonadjacent neighbours. At first sight, there seem to be a great variety of types of claw-free graphs. For instance, there are line graphs, the graph of the icosahedron, complements of triangle-free graphs, and the Schläfli graph (an amazingly highly-symmetric graph with 27 vertices), and more; for instance, if we arrange vertices in a circle, choose some intervals from the circle, and make the vertices in each interval adjacent to each other, the graph we produce is claw-free. There are several other such examples, which we regard as “basic” claw-free graphs.

Nevertheless, it is possible to prove a complete structure theorem for claw-free graphs. We have shown that every connected claw-free graph can be obtained from one of the basic claw-free graphs by simple expansion operations. In this paper we explain the precise statement of the theorem, sketch the proof, and give a few applications.

Introduction

A graph is claw-free if no vertex has three pairwise nonadjacent neighbours. (Graphs in this paper are finite and simple.) Line graphs are claw-free, and it has long been recognized that claw-free graphs are an interesting generalization of line graphs, sharing some of the same properties. For instance, Minty [16] showed in 1980 that there is a polynomial-time algorithm to find a stable set of maximum weight in a claw-free graph, generalizing the algorithm of Edmonds [9, 10] to find a maximum weight matching in a graph.

• pp. i-iv

• pp. v-vi

• pp. vii-viii

• pp. 1-28

• pp. 29-56

• pp. 57-82

• pp. 83-94

• pp. 95-118

• pp. 119-152

• pp. 153-172

• pp. 173-226

• pp. 227-258