Since 2014
Linear Time Recognition of P4-Indifferent Graphs
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
Linear Time Recognition of P4-Indifferent Graphs
|
|
| Creator |
Rizzi, Romeo
|
|
| Description |
A simple graph is P4-indifferent if it admits a total order < onits nodes such that every chordless path with nodes a, b, c, d and edgesab, 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 interms of forbidden induced subgraphs. We clarify their proof and describe a linear time algorithm to recognize P4-indifferent graphs. Whenthe input is a P4-indifferent graph, then the algorithm computes an order < as above.Key words: P4-indifference, linear time, recognition, modular decomposition.
|
|
| Publisher |
Aarhus University
|
|
| Contributor |
—
|
|
| Date |
1999-12-08
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion — |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/20107
10.7146/brics.v6i38.20107 |
|
| Source |
BRICS Report Series; No 38 (1999): RS-38 Linear Time Recognition of P4-Indifferent Graphs
BRICS Report Series; No 38 (1999): RS-38 Linear Time Recognition of P4-Indifferent Graphs 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/20107/17726
|
|
| Rights |
Copyright (c) 2015 BRICS Report Series
|
|