Title: A linear-time recognition algorithm for P 4-reducible graphs
Abstract: P4-reducible graphs are precisely the graphs none of whose vertices belong to more than one chordless path with three edges. As it turns out, the class of P4-reducible graphs strictly contains the well-known class of cographs. A remarkable property of P4-reducible graphs is their unique tree representation up to isomorphism. In this paper we present a linear-time algorithm to recognize P4-reducible graphs and to construct their corresponding tree representation.