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, Maffray 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.
On the Recognition of P_4-Indifferent Graphs
RIZZI, ROMEO
2001-01-01
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, Maffray 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
