Linear Time Recognition of P4-Indifferent Graphs

  • Romeo Rizzi

Abstract

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 a < b < c < d or a > 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.

 

Published
1999-12-08
How to Cite
Rizzi, R. (1999). Linear Time Recognition of P4-Indifferent Graphs. BRICS Report Series, 6(38). https://doi.org/10.7146/brics.v6i38.20107