A simple graph is P_4-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 ac>d. P_4-indifferent graphs generalize indifferent graphs and are perfectly orderable. Recently, Hoang, Maffray and Noy gave a characterization of P_4-indifferent graphs in terms of forbidden induced subgraphs. We clarify their proof and describe a linear time algorithm to recognize P_4-indifferent graphs. When the input is a P_4-indifferent graph, then the algorithm computes an order < as above.
On the Recognition of P4-Indifferent Graphs / Rizzi, Romeo. - ELETTRONICO. - (2001), pp. 1-9.
On the Recognition of P4-Indifferent Graphs
Rizzi, Romeo
2001-01-01
Abstract
A simple graph is P_4-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 ac>d. P_4-indifferent graphs generalize indifferent graphs and are perfectly orderable. Recently, Hoang, Maffray and Noy gave a characterization of P_4-indifferent graphs in terms of forbidden induced subgraphs. We clarify their proof and describe a linear time algorithm to recognize P_4-indifferent graphs. When the input is a P_4-indifferent graph, then the algorithm computes an order < as above.| File | Dimensione | Formato | |
|---|---|---|---|
|
tec51.pdf
accesso aperto
Tipologia:
Versione editoriale (Publisher’s layout)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
315.61 kB
Formato
Adobe PDF
|
315.61 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione
