Discrete Mathematics & Theoretical Computer Science, Vol 4, No 2 (2001)

Font Size:  Small  Medium  Large

Linear time recognition of P4-indifference graphs

Michel Habib, Christophe Paul, Laurent Viennot

Abstract


A graph is a P4-indifference graph if it admits an ordering < on its vertices such that every chordless path with vertices a, b, c, d and edges ab, bc, cd has a<b<c<d or d<c<b<a. We present a linear time recognition for these graphs.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page