Claw-free graphs. IV: Decomposition theorem (Q947722): Difference between revisions

As the title implies this is the fourth of a series of papers with the objective of giving a useful decomposition of claw-free graphs. The final decomposition is given in this paper. The three preceding papers are the following: Claw-free graphs I. Orientable prismatic graph, Claw-free graphs II. Non-orientable prismatic graphs, and Claw-free graphs III. Circular interval graphs, all of which appeared in J. Combin. Theory, Ser. B 97, No. 6, 867--903 (2007; Zbl 1128.05031), 98, No. 2, 249--290 (2008; Zbl 1137.05040), and 98, No. 4, 812--834 (2008; Zbl 1158.05035), respectively. The main decomposition theorem, which is built on the decompositions and characterizations of the three previous papers, is that a claw-free graph (actually they define a slight generalization, which is a claw-free trigraph) is either i) in one of a class of \(8\) graphs \({\mathcal S}_0, {\mathcal S}_1, {\mathcal S}_2, {\mathcal S}_3, {\mathcal S}_4, {\mathcal S}_5, {\mathcal S}_6, {\mathcal S}_7\) or ii) admits one of five types of joins. The classes \({\mathcal S}_i\) come from characterizations described in the previous series of paper such as line graphs, graphs from the icosahedron, circular interval graphs, modifications of \(L(K_6)\), and antiprismatic and near-antiprismatic graphs.