Summary: C. T. Hoàng and B. A. Reed defined in [J. Graph Theory 13, No. 4, 445–463 (1989; Zbl 0676.05071)] the classes of Raspail (also known as bipolarizable) and \(P _{4}\)-simplicial graphs, both of which are perfectly orderable, and proved that they admit polynomial-time recognition algorithms. In this paper, we consider the recognition problem on these classes of graphs and present algorithms that solve it in \(O(n m)\) time, where \(n\) and \(m\) are the numbers of vertices and of edges of the input graph. In particular, we prove properties and show that we can produce bipolarizable and \(P _{4}\)-simplicial orderings on the vertices of a graph \(G\), if such orderings exist, working only on \(P _{3}\)s that participate in \(P _{4}\)s of \(G\). The proposed recognition algorithms are simple, use simple data structures and require \(O(n+m)\) space. Moreover, we present a diagram on class inclusions and the currently best recognition time complexities for a number of perfectly orderable classes of graphs and some preliminary results on forbidden subgraphs for the class of \(P _{4}\)-simplicial graphs.
For the entire collection see [Zbl 1029.00043].