Random walks and forbidden minors III: poly(d/ε)-time partition oracles for minor-free graph classes

Akash Kumar, C. Seshadhri, Andrew Stolman

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs i…