Multi-layer analogue of Meyniel's conjecture

From papers

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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.