Containability bound by cop number and maximum degree

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.

Sources & referencesView supporting material

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.