Odd-Sum Colorings of Planar Graphs

A \emph{coloring} of a graph $G$ is a map $f:V(G)\to {\mathbb{Z}}^{+}$ such that $f(v)\mathrm{\ne }f(w)$ for all $vw\in E(G)$. A coloring $f$ is an \emph{odd-sum} coloring if ${\sum }_{w\in N[v]}f(w)$ is odd, for each vertex $v\in V(G)$. The \emph{odd-sum chromatic number} of a graph $G$, denoted ${\chi }_{os}(G)$, is the minimum number of colors used (that is, the minimum size of the range) in an odd-sum coloring of $G$. Caro, Petruševski, and Škrekovski showed, among other results, that ${\chi }_{os}(G)$ is well-defined for every finite graph $G$ and, in fact, ${\chi }_{os}(G)\le 2\chi (G)$. Thus, ${\chi }_{os}(G)\le 8$ for every planar graph $G$ (by the 4 Color Theorem), ${\chi }_{os}(G)\le 6$ for every triangle-free planar graph $G$ (by Grötzsch’s Theorem), and ${\chi }_{os}(G)\le 4$ for every bipartite graph. Caro et al. asked, for every even $\mathrm{\Delta }\ge 4$, whether there exists $g_{\mathrm{\Delta }}$ such that if $G$ is planar with maximum degree $\mathrm{\Delta }$ and girth at least $g_{\mathrm{\Delta }}$ then ${\chi }_{os}(G)\le 5$. They also asked, for every even $\mathrm{\Delta }\ge 4$, whether there exists $g_{\mathrm{\Delta }}$ such that if $G$ is planar and bipartite with maximum degree $\mathrm{\Delta }$ and girth at least $g_{\mathrm{\Delta }}$ then ${\chi }_{os}(G)\le 3$. We answer both questions negatively. We also refute a conjecture they made, resolve one further problem they posed, and make progress on another.