Unavoidable pivot-minors in graphs of large rank-depth
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_ | 1866913945769476096 |
|---|---|
| author | Ahn, Jungho Hendrey, Kevin Kwon, O-joung Oum, Sang-il |
| author_facet | Ahn, Jungho Hendrey, Kevin Kwon, O-joung Oum, Sang-il |
| contents | Shrub-depth and rank-depth are related graph parameters that are dense analogs of tree-depth. We prove that for every positive integer $t$, every graph of sufficiently large rank-depth contains a pivot-minor isomorphic to a path on $t$ vertices or a graph consisting of two disjoint cliques of size $t$ joined by a half graph. This answers an open problem raised by Kwon, McCarty, Oum, and Wollan in 2021. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_12697 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Unavoidable pivot-minors in graphs of large rank-depth Ahn, Jungho Hendrey, Kevin Kwon, O-joung Oum, Sang-il Combinatorics 05C50, 05C75, 05C83 Shrub-depth and rank-depth are related graph parameters that are dense analogs of tree-depth. We prove that for every positive integer $t$, every graph of sufficiently large rank-depth contains a pivot-minor isomorphic to a path on $t$ vertices or a graph consisting of two disjoint cliques of size $t$ joined by a half graph. This answers an open problem raised by Kwon, McCarty, Oum, and Wollan in 2021. |
| title | Unavoidable pivot-minors in graphs of large rank-depth |
| topic | Combinatorics 05C50, 05C75, 05C83 |
| url | https://arxiv.org/abs/2507.12697 |