Cops and robbers on 2K2-free graphs

被引:4
作者
Turcotte, Jeremie [1 ]
机构
[1] Univ Montreal, Dept Math & Stat, Montreal, PQ, Canada
基金
加拿大自然科学与工程研究理事会;
关键词
Cops and robbers; Cop number; Forbidden induced subgraphs; Co-diamond-free graphs; 2K(2)-free graphs; GAME; PURSUIT; NUMBER;
D O I
10.1016/j.disc.2021.112660
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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. (c) 2021 Elsevier B.V. All rights reserved.
引用
收藏
页数:9
相关论文
共 26 条