Improved bounds on the cop number when forbidding a minor

Abstract Andreae proved that the cop number of connected ‐minor‐free graphs is bounded for every graph . In particular, the cop number is at most if contains no isolated vertex, where . The main result of this paper is an improvement on this bound, which is most significant when is small or sparse, for instance, when 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 ‐minor‐free graphs, ‐minor‐free graphs and linklessly embeddable graphs.

Authors

Institutions

Publication Details

Journal
Journal of Graph Theory
Published
2024-10-13
DOI
https://doi.org/10.1002/jgt.23194
Primary Topic
Optimization and Packing Problems
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Improved bounds on the cop number when forbidding a minor

Franklin Kenter, Erin Meger, Jérémie Turcotte
Journal of Graph Theory
Optimization and Packing Problems
article

Improved bounds on the cop number when forbidding a minor

Franklin Kenter, Erin Meger, Jérémie Turcotte
article en

Abstract

Abstract Andreae proved that the cop number of connected ‐minor‐free graphs is bounded for every graph . In particular, the cop number is at most if contains no isolated vertex, where . The main result of this paper is an improvement on this bound, which is most significant when is small or sparse, for instance, when 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 ‐minor‐free graphs, ‐minor‐free graphs and linklessly embeddable graphs.

Journal of Graph TheoryVol. 108(3)
United States Naval Academy (US), Queen's University (CA), McGill University (CA)
National Science Foundation, Natural Sciences and Engineering Research Council of Canada, Office of Naval Research
Openalex Percentile: Top 75%
Optimization and Packing Problems
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Improved bounds on the cop number when forbidding a minor — Franklin Kenter, Erin Meger, et al. · Journal of Graph Theory (2024) | TGRS Research Map | TGRS