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
2026年份
5被引次数
摘要
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 .
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。
它引用的顶会 Paper2
相关 Paper
- The Grid-Minor Theorem RevisitedVida Dujmovic, Robert Hickingbotham, Jedrzej Hodor, Gwenaël Joret 等SODA 2024 · 被引用 3 次
- 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 次
- Polynomial bounds for the Graph Minor Structure TheoremMaximilian Gorsky, Michal T. Seweryn, Sebastian WiederrechtFOCS 2025 · 被引用 1 次
- Proof of the Clustered Hadwiger ConjectureVida Dujmovic, Louis Esperet, Pat Morin, David R. WoodFOCS 2023 · 被引用 7 次
