A simple linear time algorithm for cograph recognition

Abstract: In this paper, we describe a new simple linear time algorithm to recognize cographs. Cographs are exactly the -free graphs (where denotes the path with 4 vertices). The recognition process works in two steps. First, we use partition refinement techniques to produce a factorizing permutation, i.e., an ordering of the vertices in which the strong modules appear consecutively. Then a very simple test algorithm is provided to check whether the given graph is a cograph, using a single sweep of the permutation obtained in the first step. [Copyright &y& Elsevier]