The Erdős-Pósa property for circle graphs as vertex-minors
Abstract
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\).
Fields of Study & Subjects
Limits and Structures in Graph Theory
Advanced Graph Theory Research
Computational Geometry and Mesh Generation
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 4930–4952
- Publication date
- 1 January 2026
- Language
- EN