Linear Time Recognition of -Indifferent Graphs
Romeo Rizzi November 1999 |

## Abstract:
A simple graph is
-indifferent if it admits a total
order on its nodes such that every chordless path with nodes
and edges has or . -indifferent graphs
generalize indifferent graphs and are perfectly orderable. Recently, Hoàng,
Maffray and Noy gave a characterization of -indifferent graphs in terms
of forbidden induced subgraphs. We clarify their proof and describe a linear
time algorithm to recognize -indifferent graphs. When the input is a
-indifferent graph, then the algorithm computes an order as
above
Available as |

Last modified: 2003-06-08 by webmaster.