Proper Minor-Closed Classes in Blowups of Fans

Abstract

Dujmović et al. [arXiv:2407.05936] showed that any $n$-vertex planar graph is contained in a $O(\sqrt{n}{\log }^2(n))$-blowup of a fan, and asked if the same holds for any $n$-vertex $K_t$-minor-free graph. We answer this in the positive, showing that such a graph is contained in a $O_t(\sqrt{n}{\log }^2(n))$-blowup of a fan.

12 pages, 2 figures