Odd coloring of sparse graphs and planar graphs (Q2689480)

Let \(G=(V(G),E(G))\) be a graph and \(c:V(G)\rightarrow \{1,\dots,k\}\) a proper coloring, i. e., \(c(u)\neq c(v)\) for every \(uv\in E(G)\). If for every vertex \(v\) with a degree at least one there exists a color \(i_v\in\{1,\dots,k\}\) that appears an odd number of times in the neighborhood of \(v\), then we call \(c\) an odd coloring with \(k\) colors. Maximum average degree \(\mathrm{mad}(G)\) of \(G\) is the biggest average degree of any subgraph of \(G\). This contribution completely resolves Cranston's conjecture that in \(G\) there exists an odd coloring with \(k\geq 4\) colors if \(\mathrm{mad}(G)\leq\frac{4k-4}{k+1}\). This conjecture is disproved for \(k=4\), while for \(k\geq 7\) a stronger version of the conjecture is proved. (The conjecture is already known to be true for \(k\in\{5,6\}\).) Some additional results are given for planar graphs.