2023/05/31 by Clow, Alexander
#05C57 (Primary) 05C48 #05D40 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2306.00220
In this paper we consider the cop number of graphs with no, or few, short cycles. We show that when G is graph of girth g and the minimum degree δ≥ 2, then c(G) = O(nlog(n)(δ-1)-\lfloor (g+1)/(4) \rfloor) as a function of n. This extends work of Frankl and implies that if G is large and dense in the sense that δ≥ n(2)/(g)+ε, then G satisfies Meyniel's conjecture, that is c(G) = O(√(n)). Moreover, it implies that if G is large and dense in the sense that there δ≥ nε, some ε>0, while also having girth g ≥ 7, then there exists an α>0 such that c(G) = O(n1-α), thereby satisfying the weak Meyniel's conjecture. Of course, this implies similar results for dense graphs with small, that is O(n1-α), numbers of short cycles, as each cycle can be broken by adding a single cop.