The cubic-order conjecture for bridge-burning capture time

About 8 years old · traced to

Let GG be an nn-vertex graph. Write cb(G)c_b(G) for its bridge-burning cop number and captb(G)\mathrm{capt}_b(G) for its bridge-burning capture time. Cubic-order conjecture. There exists an nn-vertex graph GG with cb(G)=1c_b(G)=1 and

captb(G)=Ω(n3).\mathrm{capt}_b(G)=\Omega(n^3).

The preceding construction establishes only a quadratic lower bound, while the paper's upper bound differs by an order of magnitude; the conjecture asserts that the upper bound has the correct order of growth.

References

Primary source

William B. Kinnersley and Eric Peterson, “Cops, robbers, and burning bridges”, arXiv:1812.09955 (2018).

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.