Answers are grounded in this paper and cite their sources.
This research shows the odd chromatic number is at most 7 in planar graphs with a maximum degree of 4, suggesting tighter limits than previously known.
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 NG(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.
No takes yet. Share an insight, caveat, or question.
Carvalho et al. (2025) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: