Apex Graphs and Cographs

Abstract

A class $\mathcal{G}$ of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by ${\mathcal{G}}^{\mathrm{apex}}$ the class of graphs $G$ that contain a vertex $v$ such that $G-v$ is in $\mathcal{G}$. We prove that if a hereditary class $\mathcal{G}$ has finitely many forbidden induced subgraphs, then so does ${\mathcal{G}}^{\mathrm{apex}}$. 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.

11 pp., 7 figures; v2 writing and figures slightly improved