Excluding K_2,t as a fat minor

2025/10/16 by Albrechtsen, Sandra, Distel, Marc, Georgakopoulos, Agelos · 1 citation
#05C10 #05C63 #05C83 #51F30 #68R12 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.2510.14644

Abstract

We prove that for every t ∈ ℕ, the graph K_2,t satisfies the fat minor conjecture of Georgakopoulos and Papasoglu: for every K∈ ℕ there exist M,A∈ ℕ such that every graph with no K-fat K_2,t minor is (M,A)-quasi-isometric to a graph with no K_2,t minor. We use this to obtain an efficient algorithm for approximating the minimal multiplicative distortion of any embedding of a finite graph into a K_2,t-minor-free graph, answering a question of Chepoi, Dragan, Newman, Rabinovich, and Vaxès from 2012.

Citations

• Asymptotic structure. II. Path-width and additive quasi-isometry
• Counterexample to the conjectured coarse grid theorem
• Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture
• A characterisation of graphs quasi-isometric to K₄-minor-free graphs
• Fat minors cannot be thinned (by quasi-isometries)
• A structural duality for path-decompositions into parts of small radius
• Graph minors and metric spaces

Cited by

• String graphs are quasi-isometric to planar graphs
• Asymptotic structure. III. Excluding a fat tree

Related

• Fat minors cannot be thinned (by quasi-isometries)
• A characterisation of graphs quasi-isometric to K₄-minor-free graphs
• Counterexample to the conjectured coarse grid theorem
• K_2,3-induced minor-free graphs admit quasi-isometry with additive distortion to graphs of tree-width at most two
• Fat minors in finitely presented groups