Lune

SODA2026Top-tier venue

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

Rutger Campbell, Jochen Pascal Gollin, Meike Hatzel, O-joung Kwon, Rose McCarty, Sang-il Oum, Sebastian Wiederrecht

2026Year
5Citations

Abstract

We prove that for any circle graph HH with at least one edge and for any positive integer kk, there exists an integer t=t(k,H)t = t(k,H) so that every graph GG either has a vertex-minor isomorphic to the disjoint union of kk copies of HH, or has a tt-perturbation with no vertex-minor isomorphic to HH. Using the same techniques, we also prove that for any planar multigraph HH, every binary matroid either has a minor isomorphic to the cycle matroid of kHkH, or is a low-rank perturbation of a binary matroid with no minor isomorphic to the cycle matroid of HH.

Ask about this paper

Your agent reads all of it.

Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.

Questions to start from

Your agent calls

Luneget_paper_fulltext

Ask in Lune

Free to start. No credit card required.

Builds on2

Related papers

Dusk over the sea between two cliffs drawn in fine vertical lines