A new mathematical preprint has tightened the answer to a pursuit question in graph theory: how many cops are needed to catch a robber moving through a graph? Its main result gives every finite median graph a cop-number upper bound based on tree-dimension, a structural graph parameter, and an equivalent coloring number from the graph’s crossing graph.
The analysis concerns mathematically defined finite, simple, undirected graphs, with graphs used in the game assumed to be connected. It compares graph-parameter bounds, including tree-dimension with isometric dimension and clique number with chromatic number.
A sharper measure for median graphs
For every finite partial cube other than the one-vertex graph K1, the authors prove that tree-dimension equals the chromatic number of its crossing graph. In plain terms, the structural quantity used in the new bound can be read as the minimum number of colors needed for that associated graph.
That identity feeds into the central theorem for finite median graphs. If M is such a graph, its cop number satisfies c(M) ≤ ⌈(tdim(M) + 1)/2⌉, or equivalently c(M) ≤ ⌈(χ(M#) + 1)/2⌉. The notation records two ways of expressing the same upper bound.
The paper says this tree-dimension estimate can be arbitrarily stronger than the previously cited estimate based on isometric dimension. It is exact for trees and keeps equality for hypercubes, so the refinement is not presented as a general loss of sharpness.
The proof works through a retraction argument. An isomorphic copy of a median graph M is treated as a retract of another median graph P, and cop-number monotonicity is then used to compare c(M) with c(P). The result is proved for median graphs; whether the same bound holds for every finite partial cube remains open.
Bounds that become exact for perfect base graphs
A second result concerns simplex graphs, written S(G), and relates their cop number to two parameters of a finite graph G. The paper places c(S(G)) between ⌈(ω(G) + 1)/2⌉ and ⌈(χ(G) + 1)/2⌉. Here ω(G) is the clique number and χ(G) is the chromatic number, so the lower and upper limits come from two standard ways of measuring structure in G.
When the base graph is perfect, those two quantities coincide and the interval collapses to an exact cop number. For a general non-perfect base graph, the result remains a pair of bounds and need not determine one exact value.
Exact counts for three graph families
The paper also settles the cop number for several named partial-cube families. Every bipartite wheel BWn has cop number 2 for n ≥ 3.
For Fibonacci cubes, the authors give the formula c(Γn) = ⌈(⌈n/2⌉ + 1)/2⌉ for every n ≥ 0. Written by residue classes, c(Γ4q), c(Γ4q+1) and c(Γ4q+2) are all q + 1, while c(Γ4q+3) is q + 2, for q ≥ 0. The four-step pattern makes the occasional extra cop visible without requiring readers to evaluate the nested ceilings.
Lucas cubes follow a slightly different pattern. Their exact cop number is c(Λn) = ⌈(⌊n/2⌋ + 1)/2⌉ = ⌊n/4⌋ + 1 for every n ≥ 0. Across four consecutive residue classes, c(Λ4q), c(Λ4q+1), c(Λ4q+2) and c(Λ4q+3) are each q + 1 for q ≥ 0.
The Lucas result closes a one-cop gap that remained in the case n ≡ 3 modulo 4. The authors do so with a block-projection strategy, which brings the general lower and upper bounds together in that remaining case.
The preprint also revises two earlier bounds
The authors say a previously cited upper bound, c(Γn) ≤ ⌈n/4⌉ for n ≥ 9, is false for Fibonacci cubes. For q ≥ 2, the exact value at n = 4q + 3 is q + 2, one higher than q + 1 = ⌈(4q + 3)/4⌉.
They make the same correction for Lucas cubes: the earlier bound c(Λn) ≤ ⌈n/4⌉ for n ≥ 9 is false, and when n = 4q with q ≥ 3 the exact value is q + 1 rather than q = ⌈n/4⌉.
What remains unsettled
The results do not establish the tree-dimension bound for all finite partial cubes, and they do not resolve the proposed equality for every daisy cube. Nor do the simplex-graph results give an exact formula for every non-perfect base graph, where the two stated bounds may differ.
The manuscript is an arXiv version 1 preprint dated 26 Aug 2026, with no journal publication reported in the supplied metadata. The work was partially supported by the National Natural Science Foundation of China under grant 12071194, and the authors declare no known competing financial interests or personal relationships that could have influenced it.
Paper data and sources
Original title: Cop numbers for subclasses of partial cubes
Authors: Zhaoman Huang, Yan-Ting Xie, Shou-Jun Xu
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text