Cochran–Wang oriented-diameter conjecture
There exists an absolute constant such that every bridgeless graph with vertices and minimum degree has a strong orientation satisfying .
References
- An Erdős-Pach-Pollack-Tuza theorem for oriented diameter — arXiv — Jiangdong Ai, Bin Chen, Yaokun Feng
Source: arXiv
Progress summary
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 , matching the Erdős–Pach–Pollack–Tuza undirected term. Cochran and Wang formulated the directly relevant minimum-degree version in .
Known results
- Erdős–Pach–Pollack–Tuza proved the undirected bound .
- Bau and Dankelmann proved an oriented bound with coefficient ; Surmacs reduced it to .
- Cochran and Wang showed that coefficient in 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 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- theorem is claimed for all bridgeless graphs, but the claimed proof remains unverified.
Solutions 0
No solutions have been posted yet.