A graph is claw-free if no vertex has three pairwise nonadjacent neighbours. In this series of papers we give a structural description of all claw-free graphs. In this paper, we achieve a major part of that goal; we prove that every claw-free graph either belongs to one of a few basic classes, or admits a decomposition in a useful way.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Claw-free graphs
- Induced subgraphs