Claw-free graphs. II: Non-orientable prismatic graphs (Q2477624)

The ultimate objective of the authors is to give a characterization of graphs that do not have an induced \(K_{1,3}\) (claw-free). A graph \(G\) is prismatic if for each triangle \(T\), every vertex in \(G\) not in \(T\) has exactly one neighbor in \(T\), so the complement of a prismatic graph is a claw-free graph. 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. In a previous companion paper [J. Comb. Theory, Ser. B 97, No. 6, 867--903 (2007; Zbl 1128.05031)] it was shown that every \(3\)-colorable prismatic graph is orientable, and a characterization of \(3\)-colorable prismatic graphs is proved. The characterization involves a decomposition (called a worn chain decomposition) with each of the terms coming from three special classes of \(3\)-colorable graphs. To describe the characterization of non-orientable prismatic graphs a menagerie of 13 classes of graphs are defined. Also, a special set of non-orientable prismatic graphs, which are called rigid graphs, are defined that have the property that the vertices not on triangles have unique neighborhoods in the sets of triangles and nonadjacent vertices have a common neighbor. The rigid graphs are the critical graphs in the characterization, since it is shown that every non-orientable prismatic graph can be obtained from a rigid graph non-orientable prismatic graph by replicating vertices not on triangles and deleting edges between such vertices. Then, it is proved that every rigid non-orientable prismatic graph is in the menagerie.