1985/11/01 by Derek G. Corneil, Yehoshua Perl, Laura K. Stewart · 8 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications #Combinatorics #Chordal graph #Mathematics #Time complexity #Cograph #Discrete mathematics #Algorithm #Computer science #Graph #1-planar graph
paper · doi:10.1137/0214065
openalex publication_date 1985/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26
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.