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
Abstract
We prove that for any circle graph with at least one edge and for any positive integer , there exists an integer so that every graph either has a vertex-minor isomorphic to the disjoint union of copies of , or has a -perturbation with no vertex-minor isomorphic to . Using the same techniques, we also prove that for any planar multigraph , every binary matroid either has a minor isomorphic to the cycle matroid of , or is a low-rank perturbation of a binary matroid with no minor isomorphic to the cycle matroid of .
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.
Builds on2
Related papers
- The Grid-Minor Theorem RevisitedVida Dujmovic, Robert Hickingbotham, Jedrzej Hodor, Gwenaël Joret et al.SODA 2024 · 3 citations
- Centered colorings in minor-closed graph classesJedrzej Hodor, Hoang La, Piotr Micek, Clément RambaudSODA 2026
- Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of RecognitionTuukka Korhonen, Daniel LokshtanovSODA 2024 · 7 citations
- Polynomial bounds for the Graph Minor Structure TheoremMaximilian Gorsky, Michal T. Seweryn, Sebastian WiederrechtFOCS 2025 · 1 citation
- Proof of the Clustered Hadwiger ConjectureVida Dujmovic, Louis Esperet, Pat Morin, David R. WoodFOCS 2023 · 7 citations
