The subdivided complete-graph conjecture for the cop number
Let be a complete graph, and let be any graph obtained from by subdividing its edges, possibly a non-uniform number of times. The cop number of , denoted by , is the minimum number of cops needed to capture a robber on .
Subdivided complete-graph conjecture. For every such graph ,
This conjecture would imply Meyniel's conjecture that every graph on vertices has cop number in . The surrounding discussion establishes an upper bound of at most 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
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.