Edge-apexing in hereditary classes of graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929276450766848 |
|---|---|
| author | Singh, Jagdeep Sivaraman, Vaidy |
| author_facet | Singh, Jagdeep Sivaraman, Vaidy |
| contents | A class $\mathcal{G}$ of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by $G^{epex}$ the class of graphs that are at most one edge away from being in $\mathcal{G}$. We note that $G^{epex}$ is hereditary and prove that if a hereditary class $\mathcal{G}$ has finitely many forbidden induced subgraphs, then so does $G^{epex}$.
The hereditary class of cographs consists of all graphs $G$ that can be generated from $K_1$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_09456 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Edge-apexing in hereditary classes of graphs Singh, Jagdeep Sivaraman, Vaidy Combinatorics Discrete Mathematics 05C75 A class $\mathcal{G}$ of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by $G^{epex}$ the class of graphs that are at most one edge away from being in $\mathcal{G}$. We note that $G^{epex}$ is hereditary and prove that if a hereditary class $\mathcal{G}$ has finitely many forbidden induced subgraphs, then so does $G^{epex}$. The hereditary class of cographs consists of all graphs $G$ that can be generated from $K_1$ 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. |
| title | Edge-apexing in hereditary classes of graphs |
| topic | Combinatorics Discrete Mathematics 05C75 |
| url | https://arxiv.org/abs/2403.09456 |