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

At least 6 years old · documented by

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.

References

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.