Forbidding the subdivided claw as a subgraph or a minor
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917246591303680 |
|---|---|
| author | Allred, Sarah Ellingham, M. N. |
| author_facet | Allred, Sarah Ellingham, M. N. |
| contents | Let $Y$ be the subdivided claw, the $7$-vertex tree obtained from a claw $K_{1,3}$ by subdividing each edge exactly once. We characterize the graphs (finite and infinite) that do not have $Y$ as a subgraph, or, equivalently, do not have $Y$ as a minor. This work was motivated by a problem involving VCD minors. A graph $H$ is a vertex contraction-deletion minor, or VCD minor, of a graph $G$ if $H$ can be obtained from $G$ by a sequence of vertex deletions or contractions of all edges incident with a single vertex. Our result is a key step in describing $K_{1,3}$-VCD-minor-free line graphs. We also characterize graphs that forbid each subtree of $Y$. We discuss the relevance of our results for Turán. numbers of trees, and pathwidth and growth constants for graphs without a particular tree as a minor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_13718 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Forbidding the subdivided claw as a subgraph or a minor Allred, Sarah Ellingham, M. N. Combinatorics 05C75, 05C83 Let $Y$ be the subdivided claw, the $7$-vertex tree obtained from a claw $K_{1,3}$ by subdividing each edge exactly once. We characterize the graphs (finite and infinite) that do not have $Y$ as a subgraph, or, equivalently, do not have $Y$ as a minor. This work was motivated by a problem involving VCD minors. A graph $H$ is a vertex contraction-deletion minor, or VCD minor, of a graph $G$ if $H$ can be obtained from $G$ by a sequence of vertex deletions or contractions of all edges incident with a single vertex. Our result is a key step in describing $K_{1,3}$-VCD-minor-free line graphs. We also characterize graphs that forbid each subtree of $Y$. We discuss the relevance of our results for Turán. numbers of trees, and pathwidth and growth constants for graphs without a particular tree as a minor. |
| title | Forbidding the subdivided claw as a subgraph or a minor |
| topic | Combinatorics 05C75, 05C83 |
| url | https://arxiv.org/abs/2510.13718 |