The maximum-degree bound for lazy cop number

From papers

Let GG be a graph on nn vertices, let Δ\Delta be its maximum degree, and let cL(G)c_L(G) denote its lazy cop number.

Maximum-degree conjecture. If

Δnk2,\Delta\geq n-k^2,

then

cL(G)k.c_L(G)\leq k.

The statement is proposed as a natural generalization of the paper's proved bound for maximum degree at least n9n-9. The source suggests that it would follow inductively from the rook graph conjecture, but does not establish it.

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

Brendan W. Sullivan, Nikolas Townsend and Mikayla Werzanski, “The 3x3 rooks graph is the unique smallest graph with lazy cop number 3”, arXiv:1606.08485 (2016).

Solutions 0

No solutions have been posted yet.