Apex Graphs and Cographs
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 su...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Georgia Southern University
2024-01-01
|
| Series: | Theory and Applications of Graphs |
| Subjects: | |
| Online Access: | https://digitalcommons.georgiasouthern.edu/tag/vol11/iss1/4/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 2470-9859 |