Unavoidable induced subgraphs of large and infinite $2$-edge-connected graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908981351415808 |
|---|---|
| author | Allred, Sarah Ellingham, M. N. |
| author_facet | Allred, Sarah Ellingham, M. N. |
| contents | In 1930, Ramsey proved that every large graph contains either a large clique or a large edgeless graph as an induced subgraph. It is well known that every large connected graph contains a long path, a large clique, or a large star as an induced subgraph. Recently Allred, Ding, and Oporowski presented the unavoidable large induced subgraphs for large and infinite $2$-connected graphs. The $2$-edge-connected (sometimes called bridgeless) graphs form an important class between connected graphs and $2$-connected graphs. In this paper we prove the existence of ubiquitous structures in $2$-edge-connected graphs known as chains of pinched super-clean ladders, and incorporate these into a presentation of the unavoidable large induced subgraphs for large and infinite $2$-edge-connected graphs. As consequences we obtain results on unavoidable large subgraphs, topological minors, minors, induced topological minors, induced minors, and Eulerian subgraphs in large and infinite $2$-edge-connected graphs. When appropriate we extend our results to multigraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_21574 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Unavoidable induced subgraphs of large and infinite $2$-edge-connected graphs Allred, Sarah Ellingham, M. N. Combinatorics 05C75, 05C55 In 1930, Ramsey proved that every large graph contains either a large clique or a large edgeless graph as an induced subgraph. It is well known that every large connected graph contains a long path, a large clique, or a large star as an induced subgraph. Recently Allred, Ding, and Oporowski presented the unavoidable large induced subgraphs for large and infinite $2$-connected graphs. The $2$-edge-connected (sometimes called bridgeless) graphs form an important class between connected graphs and $2$-connected graphs. In this paper we prove the existence of ubiquitous structures in $2$-edge-connected graphs known as chains of pinched super-clean ladders, and incorporate these into a presentation of the unavoidable large induced subgraphs for large and infinite $2$-edge-connected graphs. As consequences we obtain results on unavoidable large subgraphs, topological minors, minors, induced topological minors, induced minors, and Eulerian subgraphs in large and infinite $2$-edge-connected graphs. When appropriate we extend our results to multigraphs. |
| title | Unavoidable induced subgraphs of large and infinite $2$-edge-connected graphs |
| topic | Combinatorics 05C75, 05C55 |
| url | https://arxiv.org/abs/2503.21574 |