The Erdős-Pósa property for circle graphs as vertex-minors
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_ | 1866916778611834880 |
|---|---|
| author | Campbell, Rutger Gollin, J. Pascal Hatzel, Meike Kwon, O-joung McCarty, Rose Oum, Sang-il Wiederrecht, Sebastian |
| author_facet | Campbell, Rutger Gollin, J. Pascal Hatzel, Meike Kwon, O-joung McCarty, Rose Oum, Sang-il Wiederrecht, Sebastian |
| contents | We prove that for any circle graph $H$ with at least one edge and for any positive integer $k$, there exists an integer $t=t(k,H)$ so that every graph $G$ either has a vertex-minor isomorphic to the disjoint union of $k$ copies of $H$, or has a $t$-perturbation with no vertex-minor isomorphic to $H$. Using the same techniques, we also prove that for any planar multigraph $H$, every binary matroid either has a minor isomorphic to the cycle matroid of $kH$, or is a low-rank perturbation of a binary matroid with no minor isomorphic to the cycle matroid of $H$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_03973 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Erdős-Pósa property for circle graphs as vertex-minors Campbell, Rutger Gollin, J. Pascal Hatzel, Meike Kwon, O-joung McCarty, Rose Oum, Sang-il Wiederrecht, Sebastian Combinatorics 05C75 We prove that for any circle graph $H$ with at least one edge and for any positive integer $k$, there exists an integer $t=t(k,H)$ so that every graph $G$ either has a vertex-minor isomorphic to the disjoint union of $k$ copies of $H$, or has a $t$-perturbation with no vertex-minor isomorphic to $H$. Using the same techniques, we also prove that for any planar multigraph $H$, every binary matroid either has a minor isomorphic to the cycle matroid of $kH$, or is a low-rank perturbation of a binary matroid with no minor isomorphic to the cycle matroid of $H$. |
| title | The Erdős-Pósa property for circle graphs as vertex-minors |
| topic | Combinatorics 05C75 |
| url | https://arxiv.org/abs/2506.03973 |