On Oriented Colourings of Graphs on Surfaces

2024/09/19 by Clow, Alexander · 2 citations
#05C15 #05C60 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2409.13076

Abstract

For an oriented graph G, the least number of colours required to oriented colour G is called the oriented chromatic number of G and denoted χ_o(G).For a non-negative integer g let χ_o(g) be the least integer such that χ_o(G) ≤ χ_o(g) for every oriented graph G with Euler genus at most g. We will prove that χ_o(g) is nearly linear in the sense that Ω((g)/(log(g))) ≤ χ_o(g) ≤ O(g log(g)). This resolves a question of the author, Bradshaw, and Xu, by improving their bounds of the form Ω(((g²)/(log(g)))^1/3) ≤ χ_o(g) and χ_o(g) ≤ O(g⁶⁴⁰⁰).

Cited by

• MAD Phase Transitions in the Oriented Chromatic Number
• A Note on Large Degenerate Induced Subgraphs in Sparse Graphs

Related

• The Oriented Chromatic Number of the Hexagonal Grid is 6
• Oriented Colouring Graphs of Bounded Degree and Degeneracy
• MAD Phase Transitions in the Oriented Chromatic Number
• Proper orientations and proper chromatic number
• Oriented Colourings of Graphs with Maximum Degree Three and Four