Multi-layer analogue of Meyniel's conjecture

About 3 years old · traced to

Let τ⩾1\tau\geqslant 1 be a fixed integer, and let GG be a connected graph on nn vertices. Write emcτ(G)\mathsf{emc}_{\tau}(G) for the extremal multi-layer cop number over multi-layer graphs on GG with τ\tau connected layers.

Multi-layer analogue of Meyniel's conjecture. For every fixed τ⩾1\tau\geqslant 1 and every connected nn-vertex graph GG, one has

emcτ(G)=o(n).\mathsf{emc}_{\tau}(G)=o(n).

If layers may be disconnected, or if the number of layers grows arbitrarily with nn, the source gives examples showing that no bound better than O(n)\mathcal{O}(n) is possible. The conjecture asks whether a sublinear bound holds when the number of connected layers is fixed.

References

Primary source

Jessica Enright, Kitty Meeks, William Pettersson and John Sylvester, “Cops and Robbers on Multi-Layer Graphs”, arXiv:2303.03962 (2023).

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.