Edited by Bridget S. Webb
Publisher: Cambridge University Press
Print Publication Year: 2005
Online Publication Date:August 2010
Online ISBN:9780511734885
Paperback ISBN:9780521615235
Chapter DOI: http://dx.doi.org/10.1017/CBO9780511734885.008
Subjects: Discrete Mathematics Information Theory and Coding
Image View Extract Fullview: Text View | Enlarge Image ‹ Previous Chapter ›Next Chapter
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
1 - Finite field models in additive combinatorics : Read PDF
pp. 1-28
2 - The subgroup structure of finite classical groups in terms of geometric configurations : Read PDF
pp. 29-56
3 - Constructing combinatorial objects via cliques : Read PDF
pp. 57-82
4 - Flocks of circle planes : Read PDF
pp. 83-94
5 - Judicious partitions and related problems : Read PDF
pp. 95-118
6 - An isoperimetric method for the small sumset problem : Read PDF
pp. 119-152
7 - The structure of claw-free graphs : Read PDF
pp. 153-172
8 - The multivariate Tutte polynomial (alias Potts model) for graphs and matroids : Read PDF
pp. 173-226
9 - The sparse regularity lemma and its applications : Read PDF
pp. 227-258