Linear Time Recognition of P4-Indifferent Graphs
Roméo Rizzi · BRICS Report Series · 1999
A simple graph is P4-indifferent if it admits a total order b > c > d. P4-indifferent graphs generalize indifferent graphs and are perfectly orderable. Recently, Hoang, Maray 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. Key words: P4-indifference, linear time, recognition, modular decomposition.