On the recognition of P4-indifferent graphs

A simple graph is P4-indifferent if it admits a total order < on its nodes such that every chordless path with nodes a,b,c,d and edges ab,bc,cd has ab>c>d. P4-indifferent graphs generalize indifferent graphs and are perfectly orderable. Recently, Hoàng; Maffray and Noy gave a characterization of P4-indifferent graphs in terms of forbidden induced subgraphs. We clarify their proof and describe a linear time algorithm to recognize P4-indifferent graphs. When the input is a P4-indifferent graph, then the algorithm computes an order < as above.