A class G of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by Gᵉᵖᵉˣ the class of graphs that are at most one edge away from being in G. We note that Gᵉᵖᵉˣ is hereditary and prove that if a hereditary class G has finitely many forbidden induced subgraphs, then so does Gᵉᵖᵉˣ. The hereditary class of cographs consists of all graphs G that can be generated from K₁ using complementation and disjoint union. Cographs are precisely the graphs that do not have the $4$-vertex path as an induced subgraph. For the class of edge-apex cographs our main result bounds the order of such forbidden induced subgraphs by 8 and finds all of them by computer search.
No takes yet. Share an insight, caveat, or question.
Singh et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: