4-cop-win graphs have at least 19 vertices
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914116596137984 |
|---|---|
| author | Turcotte, Jérémie Yvon, Samuel |
| author_facet | Turcotte, Jérémie Yvon, Samuel |
| contents | We show that the cop number of any graph on 18 or fewer vertices is at most 3. This answers a question posed by Andreae in 1986, as well as more recently by Baird et al. We also find all 3-cop-win graphs on 11 vertices, narrow down the possible 4-cop-win graphs on 19 vertices and make some progress on finding the minimum order of 3-cop-win planar graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2006_02998 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | 4-cop-win graphs have at least 19 vertices Turcotte, Jérémie Yvon, Samuel Combinatorics Discrete Mathematics 05C57 (Primary) 05C35, 05C85, 90C35, 68V05 (Secondary) We show that the cop number of any graph on 18 or fewer vertices is at most 3. This answers a question posed by Andreae in 1986, as well as more recently by Baird et al. We also find all 3-cop-win graphs on 11 vertices, narrow down the possible 4-cop-win graphs on 19 vertices and make some progress on finding the minimum order of 3-cop-win planar graphs. |
| title | 4-cop-win graphs have at least 19 vertices |
| topic | Combinatorics Discrete Mathematics 05C57 (Primary) 05C35, 05C85, 90C35, 68V05 (Secondary) |
| url | https://arxiv.org/abs/2006.02998 |