Apex Graphs and Cographs

Abstract

A class G of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by G^{apex} the class of graphs G that contain a vertex v such that G − v is in G. Borowiecki, Drgas-Burchardt, and Sidorowicz proved that if a hereditary class G has finitely many forbidden induced subgraphs, then so does G^{apex}. We provide an elementary proof of this result. The hereditary class of cographs consists of all graphs G that can be generated from K_1 using complementation and disjoint union. A graph is an apex cograph if it contains a vertex whose deletion results in a cograph. Cographs are precisely the graphs that do not have the 4-vertex path as an induced subgraph. Our main result finds all such forbidden induced subgraphs for the class of apex cographs.

Keywords

• apex graph
• cograph
• forbidden induced subgraph