Improved bounds on the cop number when forbidding a minor

2023/02/28 by Kenter, Franklin, Meger, Erin, Turcotte, Jérémie · 2 citations
#05C10 (Secondary) #05C57 (Primary) 05C83 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2302.14851

Abstract

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, where h∈ V(H). 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,t-minor-free graphs, K_2,t-minor-free graphs and linklessly embeddable graphs.

Cited by

• Cops and Robbers on Graphs with Path Constraints
• Cops and Robbers, Clique Covers, and Induced Cycles

Related

• Cop number of 2K₂-free graphs
• Cops and robbers on 2K₂-free graphs
• Cops and Robbers on Graphs with Path Constraints
• The Cop Number of Graphs with Forbidden Induced Subgraphs
• On the cop number of toroidal graphs