New bound on the odd chromatic number of planar graphs with maximum degree at most 4 - Carvalho, Vinícius de Souza; Lintzmayer, Carla Negri; Sambinelli, Maycon (Anais do Encontro de Teoria da Computação (ETC); 2025: Anais do X Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2025.9399, 2025)
An odd coloring of a graph G is a proper vertex coloring where, for every vertex v ∈ V (G), there is a color that appears an odd number of times in N G (v). The smallest k for which G admits an odd coloring is the (proper) odd chromatic number and it is denoted χ o (G). This coloring was introduced in 2022, and it was conjectured that χ o (G) ≤ 5 for every planar graph G, while the best known upper bound is χ o (G) ≤ 8. It is also known that any graph G satisfies χ o (G) ≤ ⌊3∆(G)/2⌋+2. This paper shows that every planar graph G with ∆(G) ≤ 4 has χ o (G) ≤ 7.