Which claw-free graphs are perfectly orderable? (Q686245)

Given an undirected graph it is perfectly orderable (p.o.) if it permits a perfect linear order \(<\) on the vertices, i.e., one such that no chordless path with vertices \(\{a,b,c,d\}\) and edges \(\{ab,bc,cd\}\) has \(a<b\) and \(d<c\). Since p.o. graphs are both interesting graphs and since recognizing them is NP-complete, determining subclasses (along with suitable algorithms) which may be determined in polynomial time is quite useful. P.o. line-graphs have been so characterized by the author. The class of p.o. complements of bipartite graphs has also been among classes characterized in this manner. A claw is an induced subgraph on \(V=\{x,a,b,c\}\) with edges \(E=\{xa,xb,xc\}\). It is shown that line-graphs and complements of bipartite graphs are claw-free. Furthermore, a complete characterization of p.o. claw-free graphs is provided by describing nine infinite families of forbidden induced subgraphs and in the development of the proof of this important theorem the wherewithal for a polynomial time recognition algorithm on the class of claw-free graphs is also created. As a byproduct a generalization of the characterization of totally balanced matrices found by Anstee and Farber, Edmonds and Lubiw, Kolen and Sakarovitch is immediate via the observation that this characterization is precisely the case of complements of bipartite graphs in the present setting.