A Quadratic Upper Bound for the Maximum Oriented Diameter With Leading Constant 1

Abstract

ABSTRACT Let be the smallest integer such that every bridgeless graph with has a strong orientation satisfying . In 1978, Chvátal and Thomassen proved . Later, Babu–Benson–Rajendraprasad–Vaka improved the upper bound to . We show that the leading constant can be reduced to 1: We also prove the explicit bound for every .