A characterization of P-4-indifference graphs

A graph is a P-4-indifference graph if it admits a linear ordering < on its vertices such that every chordless path with vertices a, b, c, d and edges ab, be, ed has either a < b < c < d or d < c < b < a. P-4-indifference gra phs generalize indifference graphs and are perfectly orderable. We give a c haracterization of P-4-difference graphs by forbidden induced subgraphs. (C ) 1999 John Wiley & Sons, Inc.