{"id":"arxiv/2611.03169","url":"https://arxiv.org/abs/2611.03169","tags":["math.CO"],"score":0,"title":"An Erdős-Pach-Pollack-Tuza theorem for oriented diameter","domain":"math.CO","source":"arxiv","authors":["Jiangdong Ai","Bin Chen","Yaokun Feng"],"reviews":0,"subject":"math.CO","summary":"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 $δ\\ge 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-02","reactions":{}}