The cubic-order conjecture for bridge-burning capture time

From papers

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.

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

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

Solutions 0

No solutions have been posted yet.