2023/06/02 by Tianjiao Dai, Dai, Tianjiao, Qiancheng Ouyang +3 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2306.01341
openalex publication_date 2023/06/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph G, a vertex-colouring σ of G, and a subset X⊆ V(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 k∈ℕ such that an odd colouring σ\colon V(G)→ [k] exists. In a recent paper, Caro, Petru\v sevski and \v Skrekovski 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(lnΔ) as Δ→ ∞. We also prove that χo(G)≤\lfloor3Δ/2\rfloor+2 for every Δ. If moreover the minimum degree δ of G is sufficiently large, we have χo(G) ≤ χ(G) + O(Δln Δ/δ) and χo(G) = O(χ(G)ln Δ). Finally, given an integer h≥ 1, we study the generalisation of these results to h-odd colourings, where every vertex v must have at least min \°(v),h\ odd colours in its neighbourhood. Many of our results are tight up to some multiplicative constant.