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

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 $\delta \ge 2$ has diameter at most $3n/(\delta +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 $\delta$ has a strong orientation of diameter at most $3n/(\delta +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.

arXiv comment35 pages, 2 figures