2025/06/04 by Rutger Campbell, Campbell, Rutger, J. Pascal Gollin +11
Computer Science · Mathematics · #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2506.03973
openalex publication_date 2025/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03
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.