On the recognition of \(P_4\)-indifferent graphs (Q5946757)

A simple graph \(G=(V,E)\) is \(P_4\)-indifferent if it admits a total order \(<\) on \(V\) such that \(a<b<c<d\) or \(d<c<b<a\) holds for every chordless path in \(G\) with vertices \(a,b,c,d\) and edges \(ab,bc,cd\). The class of \(P_4\)-indifference graphs sandwiches between the subclass of proper interval graphs and the superclass of perfectly orderable graphs. \textit{C. T. Hoàng, F. Maffray} and \textit{M. Noy} [J. Graph Theory 31, No. 3, 155-162 (1999; Zbl 0929.05073)] characterised \(P_4\)-indifference graphs by forbidden induced subgraphs. The paper outlines a linear time algorithm for recognising \(P_4\)-indifference graphs and computing the corresponding vertex orders. Another such algorithm was forged by \textit{M. Habib, C. Paul} and \textit{L. Viennot} [Discrete Math. Theor. Comput. Sci. 4, No. 2, 173-178 (2001)].