The subdivided complete-graph conjecture for the cop number

At least 17 years old · documented by

Let KnK_n be a complete graph, and let GG be any graph obtained from KnK_n by subdividing its edges, possibly a non-uniform number of times. The cop number of GG, denoted by cop⁡(G)\operatorname{cop}(G), is the minimum number of cops needed to capture a robber on GG.

Subdivided complete-graph conjecture. For every such graph GG,

cop⁡(G)∈O(n).\operatorname{cop}(G)\in O(\sqrt n).

This conjecture would imply Meyniel's conjecture that every graph on nn vertices has cop number in O(n)O(\sqrt n). The surrounding discussion establishes an upper bound of at most 22 for the uniformly subdivided complete graph considered in the construction, but does not resolve the conjecture for arbitrary subdivisions.

References

Primary source

Gwenaël Joret, Marcin Kamiński and Dirk Oliver Theis, “The Cops and Robber game on graphs with forbidden (induced) subgraphs”, arXiv:0804.4145 (2008).

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.