The odd coloring of some Cartesian product graphs

An odd $c$-coloring of a graph is a proper $c$-coloring such that each non-isolated vertex has at least one color appearing an odd number of times in its neighborhood. The minimum number of colors in any odd coloring of $G$, denoted ${\chi }_o(G)$, is called the odd chromatic number. This concept was introduced by Petruševski and Škrekovski, who conjectured that every planar graph $G$ is odd 5-colorable and observed that ${\chi }_o(G◻H)\le {\chi }_o(G)\cdot {\chi }_o(H)$ for connected nontrivial graphs $G$ and $H$. In this paper, for specific Cartesian product graphs $G◻H$, such as $P_m◻P_n$, $C_m◻P_n$, and $C_m◻C_n$, we determine the exact value of ${\chi }_o(G◻H)$, which establishes tighter upper bounds than the multiplicative bound ${\chi }_o(G)\cdot {\chi }_o(H)$. We show that ${\chi }_o(P_m◻P_n)\le 4$ with a complete characterization of all cases; ${\chi }_o(C_m◻P_n)\le 5$ with a full classification for even and odd $m$; and ${\chi }_o(C_m◻C_n)\le 5$ with necessary and sufficient conditions for 3-, 4-, and 5-colorability under parity and divisibility constraints. These results significantly improve upon the multiplicative upper bound and provide new constructive methods and theoretical insights for studying odd colorings in Cartesian product graphs. Additionally, we determine that ${\chi }_o(K_m◻P_n)={\chi }_o(K_m◻C_n)=m$ for $m=3$ and $C_n$ is an even cycle or $m\ge 4$.