Romeo Rizzi

2001, Note: Published in: "Discrete Mathematics" 239 (2001) 161--169

Keywords: P_4-indifference, linear time, recognition, modular decomposition

Abstract:A simple graph is P_4-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 a<b<c<d or a>b>c>d. P_4-indifferent graphs generalize indifferent graphs and are perfectly orderable. Recently, Hoang, Maffray and Noy gave a characterization of P_4-indifferent graphs in terms of forbidden induced subgraphs. We clarify their proof and describe a linear time algorithm to recognize P_4-indifferent graphs. When the input is a P_4-indifferent graph, then the algorithm computes an order < as above.