The Erdős-Pósa property for circle graphs as vertex-minors

View at publisher
Authors: Rutger Campbell, J. Pascal Gollin, Meike Hatzel, O‐joung Kwon, Rose McCarty, Sang‐il Oum, Sebastian Wiederrecht
Cited by: 0

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