Odd Colorings of Sparse Graphs

Daniel W. Cranston

Published 2022-01-05Version 1

A proper coloring of a graph is called \emph{odd} if every non-isolated vertex has some color that appears an odd number of times on its neighborhood. The smallest number of colors that admits an odd coloring of a graph $G$ is denoted $\chi_o(G)$. This notion was introduced by Petru\v{s}evski and \v{S}krekovski, who proved that if $G$ is planar then $\chi_o(G)\le 9$; they also conjectured that $\chi_o(G)\le 5$. For a positive real number $\alpha$, we consider the maximum value of $\chi_o(G)$ over all graphs $G$ with maximum average degree less than $\alpha$; we denote this value by $\chi_o(\mathcal{G}_{\alpha})$. We note that $\chi_o(\mathcal{G}_{\alpha})$ is undefined for all $\alpha\ge 4$. In contrast, for each $\alpha\in[0,4)$, we give a (nearly sharp) upper bound on $\chi_o(\mathcal{G}_{\alpha})$. Finally, we prove $\chi_o(\mathcal{G}_{20/7})= 5$ and $\chi_o(\mathcal{G}_3)= 6$. Both of these results are sharp.