August 11, 2025

New bound on the odd chromatic number of planar graphs with maximum degree at most 4

Key Points

Every planar graph with a maximum degree of 4 has an odd chromatic number less than or equal to 7, confirming a new upper limit.
The research demonstrates that this upper bound is an improvement over the previous best known limit of 8 for planar graphs.
Using principles of proper vertex coloring, the study offers significant insights into the properties of planar graphs and their colorings.
The findings highlight the conjectured relationship between maximum degree and chromatic numbers in planar graph theory.

Abstract

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.

Bookmark

Cite This Study

Carvalho et al. (Thu,) studied this question.

synapsesocial.com/papers/68a35ee30a429f7973327ace https://doi.org/https://doi.org/10.5753/etc.2025.9399

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

Bookmark