Weak Meyniel's conjecture on the cop number of arbitrary graphs

Let GG be a graph of order nn, and let c(G)c(G) denote its cop number. Weak Meyniel's conjecture. There exists an ε>0\varepsilon>0 such that

c(G)=O(n1ε).c(G)=O(n^{1-\varepsilon}).

This weaker form of Meyniel's conjecture, also known as the Soft Meyniel conjecture, remains widely open and seeks a sublinear upper bound on the cop number of every graph.

Sources & referencesView supporting material

Primary source

Seyyed Aliasghar Hosseini, Bojan Mohar and Sebastian Gonzalez Hermosillo de la Maza, “Meyniel's conjecture on graphs of bounded degree”, arXiv:1912.06957 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.