Improved bounds on the cop number when forbidding a minor

02/28/2023

∙

by   Franklin Kenter, et al.

∙

0

∙

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.