Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs

Ittai Abraham, Cyril Gavoille, Anupam Gupta +2

We prove that any graph excluding $K_r$ as a minor has can be partitioned into clusters of diameter at most $\Delta$ while removing at most $O(r/\Delta )$ fraction of the edges. This improves…