Claw-free graphs. I: Orientable prismatic graphs (Q2384800)

The overall objective of the authors is to give a characterization of claw-free graphs (graphs that do not have an induced \(K_{1,3}\) subgraph). A graph \(G\) is prismatic if for each triangle \(T\), every vertex in \(G\) not in \(T\) has exactly one neighbor in \(T\). The complement of a prismatic graph is a claw-free graph, so a characterization of prismatic graphs is one step in the characterization of claw-free graphs. A prismatic graph is orientable if each of the triangles has an orientation and these orientations on disjoint triangles are compatible with the matching that exists between the triangles. It is shown that every \(3\)-colorable prismatic graph is orientable. A characterization of \(3\)-colorable prismatic graphs is given by showing that such graphs admit a decomposition (called a worn chain decomposition) with each of the terms coming from one of three classes of graphs of \(3\)-colorable graphs \({\mathcal Q}_0\), \({\mathcal Q}_1\), and \({\mathcal Q}_2\). The graphs in \({\mathcal Q}_0\) have no triangles, the graphs in \({\mathcal Q}_1\) are isomorphic to the line graphs of \(K_{3,3}\), and the graphs in \({\mathcal Q}_2\) are a canonically-colored path of triangle graphs.