A characterisation of graphs quasi-isometric to K₄-minor-free graphs

2024/08/27 by Albrechtsen, Sandra, Jacobs, Raphael W., Knappe, Paul +1 · 5 citations
#05C10 #05C83 #51F30 #Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.2408.15335

Abstract

We prove that there is a function f such that every graph with no K-fat K₄ minor is f(K)-quasi-isometric to a graph with no K₄ minor. This solves the K₄-case of a general conjecture of Georgakopoulos and Papasoglu. Our proof technique also yields a new short proof of the respective K₄^--case, which was first established by Fujiwara and Papasoglu.

Cited by

• String graphs are quasi-isometric to planar graphs
• Burling graphs in graphs with large chromatic number
• Excluding K_2,t as a fat minor
• Induced Minors, Asymptotic Dimension, and Baker's Technique
• An improved quasi-isometry between graphs of bounded cliquewidth and graphs of bounded treewidth

Related

• Excluding K_2,t as a fat minor
• Fat minors cannot be thinned (by quasi-isometries)
• Quasi-transitive 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