2026/07/24 by Alexander Clow
#math.CO
For an oriented graph G the oriented chromatic number of G, written χo(G), is the least integer t such that G has a homomorphism to a tournament on t vertices. The oriented chromatic number of a simple graph H is the maximum oriented chromatic number over all orientations of H. Borodin, Kostochka, Nešetřil, Raspaud, and Sopena proved in 1999 that for all ε>0, graphs with maximum average degree less than 4-ε have bounded oriented chromatic number. This is in some sense optimal, because 1-subdivisions of cliques demonstrate that there exists graphs with maximum average degree strictly less than 4 and oriented chromatic number Ω(√(n)). We prove that for every positive integer d, every d-degenerate graph G with sufficiently large order satisfies χo(G) ≤ 6(1+(9d2)/(4))(1)/(2)d 8d√(n). This implies for a fixed r≥ 4, the optimal bound for the oriented chromatic number of graphs with maximum average degree less than r is Θ(√(n)). This complements a bound of Wood, who showed that for all n vertex graphs χo ≤ 2Δ√(n-1) where Δ is the maximum degree.