Cops and robbers on 2K₂-free graphs

2020/01/09 by Turcotte, Jérémie · 2 citations
#05C38 #05C57 (Primary) 05C75 #91A43 (Secondary) #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2001.03124

Abstract

We prove that the cop number of any 2K₂-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₁+K₂-free (co-diamond--free) graphs is best possible.

Cited by

• Cops and Robbers on Graphs with Path Constraints
• Cops and Robbers, Clique Covers, and Induced Cycles

Related

• Cop number of 2K₂-free graphs
• Cops and robber on subclasses of P₅-free graphs
• Cops and Robbers on Graphs with Path Constraints
• Cops and robbers on P₅-free graphs
• 4K₁-free graph with the cop number 3