Random walks and forbidden minors II: A $\text{poly}(d{\epsilon }^{-1})$-query tester for minor-closed properties of bounded-degree graphs

Akash Kumar, C. Seshadhri, Andrew Stolman

Let $G$ be a graph with $n$ vertices and maximum degree $d$. Fix some minor-closed property $\mathcal{P}$ (such as planarity). We say that $G$ is $\epsilon$-far from $\mathcal{P…