2026/06/05 by Alexander Clow, Imed Zaguia
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Complexity and Algorithms in Graphs
paper · doi:10.1016/j.disc.2026.115252
We consider the Cops and Robbers game played on finite simple graphs. In a graph G , the number of cops required to capture the robber in the Cops and Robbers game is denoted by c ( G ) . For all graphs G it is simple to see that c ( G ) ≤ α ( G ) ≤ θ ( G ) where α ( G ) and θ ( G ) are the independence number and clique cover number respectively. In 2022 Turcotte asked if c ( G ) < α ( G ) for all graphs with α ( G ) ≥ 3 . Recently, Char, Maniya, and Pradhan proved this is false when α = 3 , by demonstrating the compliment of the Shrikhande graph has cop number and independence number 3. When α > 3 the problem remains open. We settle this problem using random graphs, by proving the stronger result that for all k ≥ 1 there exists a graph G such that c ( G ) = α ( G ) = θ ( G ) = k . Next, we consider the structure of graphs with c ( G ) = θ ( G ) ≥ 3 . We prove, using structural arguments, that any graphs G which satisfies c ( G ) = θ ( G ) = k ≥ 3 contain induced cycles of all lengths 3 ≤ t ≤ k + 1 . This implies all perfect graphs G with α ( G ) ≥ 4 have c ( G ) < α ( G ) . Additionally, we discuss whether typical triangle-free and C 4 -free graphs will have c ( G ) < α ( G ) .