A linear recognition algorithm for cographs. (English) Zbl 0575.68065

Corneil, D. G.; Perl, Y.; Stewart, L. K.

SIAM J. Comput. 14, 926-934 (1985).

Cographs are the graphs formed from a single vertex under the closure of the operations of union and complement. Another characterization of cographs is that they are the undirected graphs with no induced paths on four vertices. Cographs arise naturally in such application areas as examination scheduling and automatic clustering of index terms. Furthermore, it is known that cographs have a unique tree representation called a cotree. Using the cotree it is possible to design very fast polynomial time algorithms for problems which are intractable for graphs in general. Such problems include chromatic number, clique determination, clustering, minimum weight domination, isomorphism, minimum fill-in and Hamiltonicity. In this paper we present a linear time algorithm for recognizing cographs and constructing their cotree representation.

MSC:

68R10

Graph theory (including graph drawing) in computer science

Keywords:

permutation graphs; perfect graphs; examination scheduling; automatic clustering of index terms; cotree; chromatic number; clique determination; minimum weight domination; isomorphism; minimum fill-in; Hamiltonicity; linear time algorithm