← All problems

Cochran–Wang oriented-diameter conjecture

There exists an absolute constant CC such that every bridgeless graph GG with n=∣V(G)∣n=|V(G)| vertices and minimum degree δ\delta has a strong orientation DD satisfying diam⁡(D)≤3nδ+1+C\operatorname{diam}(D)\le \frac{3n}{\delta+1}+C.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

An unrefereed preprint claims to settle the conjecture for every bridgeless graph, but the result has not been independently checked.

The conjecture asks whether strong orientations of every bridgeless graph satisfy the sharp oriented-diameter bound with leading coefficient 33, matching the Erdős–Pach–Pollack–Tuza undirected term. Cochran and Wang formulated the directly relevant minimum-degree version in 20242024.

Known results

  • Erdős–Pach–Pollack–Tuza proved the undirected bound diam⁡(G)≤3n/(δ+1)+O(1)\operatorname{diam}(G)\le 3n/(\delta+1)+O(1).
  • Bau and Dankelmann proved an oriented bound with coefficient 1111; Surmacs reduced it to 77.
  • Cochran and Wang showed that coefficient 11 in c⋅3n/(δ+1)+O(1)c\cdot 3n/(\delta+1)+O(1) is optimal for minimum-degree formulations, with a matching lower-bound family.

November 2026 claimed resolution

Ai, Chen, and Feng’s preprint claims the coefficient 33 for all bridgeless graphs, with an explicit absolute additive constant. The claim is unrefereed and no independent verification was found.

Current status (as of November 2026): The coefficient-33 theorem is claimed for all bridgeless graphs, but the claimed proof remains unverified.

Sources

Solutions 0

No solutions have been posted yet.