Cop number of 2K₂-free graphs

2019/03/27 by Vaidy Sivaraman, Sivaraman, Vaidy, Stephen M. Testa +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1903.11484

openalex publication_date 2019/03/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that the cop number of a 2K₂-free graph is at most 2 if it has diameter 3 or does not have an induced cycle of length k, where k ∈ \3,4,5\. We conjecture that the cop number of every 2K₂-free graph is at most 2.

Citations

• Vertex-to-vertex pursuit in a graph

Cited by

• Cops and Robbers on Graphs with Path Constraints

Related

• Cops and robbers on 2K₂-free graphs
• Improved bounds on the cop number when forbidding a minor
• Cops and Robbers on Graphs with Path Constraints
• Cops and robbers on P₅-free graphs
• Cops and robber on subclasses of P₅-free graphs