Improved bounds on the cop number when forbidding a minor
share
Andreae (1986) proved that the cop number of connected H-minor-free graphs is bounded for every graph H. In particular, the cop number is at most |E(H-h)| if H-h contains no isolated vertex. The main result of this paper is an improvement on this bound, which is most significant when H is small or sparse, for instance when H-h can be obtained from another graph by multiple edge subdivisions. Some consequences of this result are improvements on the upper bound for the cop number of K_3,m-minor-free graphs, K_2,m-minor free graphs and linklessly embeddable graphs.
READ FULL TEXT