Improved bounds on the cop number when forbidding a minor
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917046245130240 |
|---|---|
| author | Kenter, Franklin Meger, Erin Turcotte, Jérémie |
| author_facet | Kenter, Franklin Meger, Erin Turcotte, Jérémie |
| contents | 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\in 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_14851 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Improved bounds on the cop number when forbidding a minor Kenter, Franklin Meger, Erin Turcotte, Jérémie Combinatorics Discrete Mathematics 05C57 (Primary) 05C83, 05C10 (Secondary) 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\in 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. |
| title | Improved bounds on the cop number when forbidding a minor |
| topic | Combinatorics Discrete Mathematics 05C57 (Primary) 05C83, 05C10 (Secondary) |
| url | https://arxiv.org/abs/2302.14851 |