The maximum-degree bound for lazy cop number

About 10 years old · traced to

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

Δ≥n−k2,\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 n−9n-9. The source suggests that it would follow inductively from the rook graph conjecture, but does not establish it.

References

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).

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.