An Erd s-Pach-Pollack-Tuza theorem for oriented diameter

arXiv:2611.03169 · math.CO · Submitted 2026-11-02 · Read on arXiv

math.CO

Submitted: 2026-11-02

Updated: 2026-11-02

Comments: 35 pages, 2 figures

License: http://creativecommons.org/licenses/by/4.0/

The gist: The oriented diameter of a bridgeless graph is the minimum diameter of its strong orientations.

Terminology

Abstract

The oriented diameter of a bridgeless graph is the minimum diameter of its strong orientations. Erdős, Pach, Pollack and Tuza proved that every connected graph of order n and minimum degree δ at least 2 has diameter at most 3n/(δ+1)-1, which is sharp up to an additive constant. Cochran and Wang conjectured that the oriented diameter obeys the same bound up to an absolute additive constant. We prove this conjecture: every bridgeless graph of order n and minimum degree δ has a strong orientation of diameter at most 3n/(δ+1)+10 17. Thus the bound of Erdős, Pach, Pollack and Tuza for the diameter carries over to the oriented diameter, with only the additive constant changed; in particular, the coefficient 3 is best possible.

Related papers