Containability bound by cop number and maximum degree

About 12 years old · traced to

Let GG be a graph. Write ξ(G)\xi(G) for its containability number, the minimum number of cops needed to contain the robber, c(G)c(G) for its cop number in the original Cops and Robbers game, and Δ(G)\Delta(G) for its maximum degree. Containability bound. For every graph GG,

ξ(G)≤Δ(G)c(G).\xi(G)\leq \Delta(G)c(G).

The paper explicitly says that the authors were unable to prove or disprove this bound; it is presented as a conjecture and remains open.

References

Primary source

Danny Crytser, Natasha Komarov and John Mackey, “Containment: A Variation of Cops and Robbers”, arXiv:1405.3330 (2019).

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.