Cops and robbers on $2K_2$-free graphs

Abstract

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.

10 pages, 1 figure

References in corpus (3)

• Cops and Robbers on Graphs with a Set of Forbidden Induced Subgraphs
• The Cop Number of Graphs with Forbidden Induced Subgraphs
• Cop number of graphs without long holes

Cited by in corpus (3)

• Cops and robbers on $P_5$-free graphs
• Structure of (bull, diamond)-free graphs and its applications
• A note on Cops and Robbers, independence number, domination number and diameter