Conjecture on the cop number of graphs embedded in non-orientable surfaces

About 18 years old · traced to

Let c(g)c(g) denote the maximum cop number of a graph embedded in an orientable surface of genus gg, and let c~(g)\tilde c(g) denote the corresponding maximum for graphs embedded in a non-orientable surface of genus gg. Surface cop-number conjecture.

c~(g)=c(⌊g/2⌋).\tilde c(g)=c(\lfloor g/2\rfloor).

The preceding argument establishes the upper bound c~(g)≤c(g−1)\tilde c(g)\leq c(g-1) using the orientable double cover, while the equality for all genera is presented as a conjecture and its status is not resolved in the supplied text.

References

Primary source

Nancy E. Clarke, Samuel Fiorini, Gwenaël Joret and Dirk Oliver Theis, “A note on the Cops & Robber game on graphs embedded in non-orientable surfaces”, arXiv:0803.0538 (2011).

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.