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

@misc{ai2026erdőspachpollacktuza,
  title = {{An Erdős-Pach-Pollack-Tuza theorem for oriented diameter}},
  author = {Jiangdong Ai and Bin Chen and Yaokun Feng},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.03169},
  eprint = {2611.03169},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.03169},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - An Erdős-Pach-Pollack-Tuza theorem for oriented diameter
AU  - Jiangdong Ai
AU  - Bin Chen
AU  - Yaokun Feng
PY  - 2026
DA  - 2026/11/02
PB  - arXiv
DO  - 10.48550/arxiv.2611.03169
UR  - https://arxiv.org/abs/2611.03169
AB  - 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 δ≥ 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.
ER  -