Xiao-Pan Lian

An improved upper bound for oriented diameter of graphs with diameter $4$

Let $f(d)$ denote the smallest integer such that every bridgeless graph of diameter $d$ admits a strong orientation with diameter at most $f(d)$. It is known that $f(2)=6$ and $f(3)=9$. For $d=4$, the classical bounds of Chv\'{a}tal and Thomassen [JCTB, 1978] imply $12\le f(4)\le40$, and subsequent work reduced the upp...