Structural Bounds and Forbidden Induced Subgraphs for Edge-Add Graph Classes
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915927530930176 |
|---|---|
| author | Singh, Jagdeep Sivaraman, Vaidy |
| author_facet | Singh, Jagdeep Sivaraman, Vaidy |
| contents | A class $\mathcal{G}$ of graphs is hereditary if it is closed under taking induced subgraphs. We investigate the edge-add class, $\mathcal{G}^{\mathrm{add}}$, consisting of graphs that can be made members of $\mathcal{G}$ by adding at most one edge. While it is known that the operations of vertex deletion and edge deletion preserve the finiteness of forbidden induced subgraphs for classes with finite exclusions, the behavior of edge addition on classes with infinite exclusions remains largely unexplored.
We characterize the edge-add class of chordal graphs by their forbidden induced subgraphs and extend the result to a general finiteness theorem: for any fixed $p\ge0$, the set of forbidden induced subgraphs for $p$-edge-add chordal graphs that are not cycles is finite. In contrast, we show that this phenomenon does not extend to perfect graphs. Furthermore, we provide explicit structural bounds proving that edge addition preserves finiteness for base classes with finitely many exclusions. We conclude by providing the complete structural characterizations and explicit minimal obstruction lists for the edge-add classes of split and threshold graphs, and generalize these results to $(p,q)$-edge split graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_20954 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Structural Bounds and Forbidden Induced Subgraphs for Edge-Add Graph Classes Singh, Jagdeep Sivaraman, Vaidy Combinatorics 05C75 A class $\mathcal{G}$ of graphs is hereditary if it is closed under taking induced subgraphs. We investigate the edge-add class, $\mathcal{G}^{\mathrm{add}}$, consisting of graphs that can be made members of $\mathcal{G}$ by adding at most one edge. While it is known that the operations of vertex deletion and edge deletion preserve the finiteness of forbidden induced subgraphs for classes with finite exclusions, the behavior of edge addition on classes with infinite exclusions remains largely unexplored. We characterize the edge-add class of chordal graphs by their forbidden induced subgraphs and extend the result to a general finiteness theorem: for any fixed $p\ge0$, the set of forbidden induced subgraphs for $p$-edge-add chordal graphs that are not cycles is finite. In contrast, we show that this phenomenon does not extend to perfect graphs. Furthermore, we provide explicit structural bounds proving that edge addition preserves finiteness for base classes with finitely many exclusions. We conclude by providing the complete structural characterizations and explicit minimal obstruction lists for the edge-add classes of split and threshold graphs, and generalize these results to $(p,q)$-edge split graphs. |
| title | Structural Bounds and Forbidden Induced Subgraphs for Edge-Add Graph Classes |
| topic | Combinatorics 05C75 |
| url | https://arxiv.org/abs/2503.20954 |