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átal and Thomassen [JCTB, 1978] imply $12\le f(4)\le40$, and subsequent work reduced the upper bound to 21. Very recently, Lin, Wang and You further established the substantially stronger bound $f(4)\le18$. Pushing this bound below $18$ turns out to be considerably more difficult, since the remaining extremal configurations cannot be handled by existing techniques based…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.29526
curl -X POST /api/v1/records/arxiv/2609.29526/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.29526/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'