The classification conjecture for ten-vertex graphs with lazy cop number three

From papers

Let GG be a graph on 10 vertices, let R3=K3K3R_3=K_3\square K_3 be the 3×33\times3 Rooks graph, and let cL(G)c_L(G) denote its lazy cop number.

Ten-vertex classification conjecture. The only graphs GG on 10 vertices with cL(G)=3c_L(G)=3 are either the Petersen graph, or a copy of R3R_3 with an additional vertex vv whose degree is at most 5 and whose adjacencies are chosen in a particular way so as not to reduce the lazy cop number to two.

The conjecture is intended to characterize the graphs needed for the paper's proposed analysis of graphs with maximum degree four. The source describes the required adjacency conditions only qualitatively, and reports no proof or resolution.

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.