Cops and robbers on $2K_2$-free graphs
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909871570419712 |
|---|---|
| author | Turcotte, Jérémie |
| author_facet | Turcotte, Jérémie |
| contents | We prove that the cop number of any $2K_2$-free graph is at most 2, proving a conjecture of Sivaraman and Testa. We also show that the upper bound of $3$ on the cop number of $2K_1+K_2$-free (co-diamond--free) graphs is best possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2001_03124 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Cops and robbers on $2K_2$-free graphs Turcotte, Jérémie Combinatorics Discrete Mathematics 05C57 (Primary) 05C75, 05C38, 91A43 (Secondary) We prove that the cop number of any $2K_2$-free graph is at most 2, proving a conjecture of Sivaraman and Testa. We also show that the upper bound of $3$ on the cop number of $2K_1+K_2$-free (co-diamond--free) graphs is best possible. |
| title | Cops and robbers on $2K_2$-free graphs |
| topic | Combinatorics Discrete Mathematics 05C57 (Primary) 05C75, 05C38, 91A43 (Secondary) |
| url | https://arxiv.org/abs/2001.03124 |