|国家预印本平台
首页|The Erd\H{o}s-P\'{o}sa property for circle graphs as vertex-minors

The Erd\H{o}s-P\'{o}sa property for circle graphs as vertex-minors

The Erd\H{o}s-P\'{o}sa property for circle graphs as vertex-minors

来源:Arxiv_logoArxiv
英文摘要

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$.

Rutger Campbell、J. Pascal Gollin、Meike Hatzel、O-joung Kwon、Rose McCarty、Sang-il Oum、Sebastian Wiederrecht

数学

Rutger Campbell,J. Pascal Gollin,Meike Hatzel,O-joung Kwon,Rose McCarty,Sang-il Oum,Sebastian Wiederrecht.The Erd\H{o}s-P\'{o}sa property for circle graphs as vertex-minors[EB/OL].(2025-06-04)[2025-07-18].https://arxiv.org/abs/2506.03973.点此复制

评论