2017/10/31 by Pierre Aboulker, Samuel Fiorini, Tony Huynh +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Conjecture #Constant (computer programming) #Existential quantification #Function (biology) #Graph #Integer (computer science) #Limits and Structures in Graph Theory #Planar #Planar graph #acm:05C75 #cs.DM #math.CO #msc:05C75
paper · pdf · doi:10.1137/17m1153169
published as SIAM J. Discrete Math. 32-3 (2018), pp. 2302-2312 · 15 pages, 1 figure
openalex created_date 2017/11/10 · openalex publication_date 2018/01/01 · arxiv created 2018/07/05 · arxiv updated 2018/10/23 · openalex updated_date 2026/08/05
Let Wt denote the wheel on t+1 vertices. We prove that for every integer t ≥ 3 there is a constant c=c(t) such that for every integer k ≥ 1 and every graph G, either G has k vertex-disjoint subgraphs each containing Wt as a minor, or there is a subset X of at most c k log k vertices such that G-X has no Wt minor. This is best possible, up to the value of c. We conjecture that the result remains true more generally if we replace Wt with any fixed planar graph H.