New Bounds for Odd Colourings of Graphs - Dai, Tianjiao; Ouyang, Qiancheng; Pirot, François (The Electronic Journal of Combinatorics, 2024)
Given a graph G, a vertex-colouring σ of G, and a subset XV(G), a colour x σ(X) is said to be odd for X in σ if it has an odd number of occurrences in X. We say that σ is an odd colouring of G if it is proper and every (open) neighbourhood has an odd colour in σ. The odd chromatic number of a graph G, denoted by χ_o(G), is the minimum kN such that an odd colouring σ V(G)→ [k] exists. In a recent paper, Caro, Petruševski and Škrekovski conjectured that every connected graph of maximum degree Δ3 has odd-chromatic number at most Δ+1. We prove that this conjecture holds asymptotically: for every connected graph G with maximum degree Δ, χ_o(G)Δ+O(Δ) as Δ → ∞. We also prove that χ_o(G)3Δ/2 floor+2 for every Δ. If moreover the minimum degree δ of G is sufficiently large, we have χ_o(G) χ(G) + O(Δ Δ/δ) and χ_o(G) = O(χ(G)Δ). Finally, given an integer h1, we study the generalisation of these results to h-odd colourings, where every vertex v must have at least {(v),h} odd colours in its neighbourhood. Many of our results are tight up to some multiplicative constant.