Additive Coloring of Planar Graphs
Tomasz Bartnicki, Bartłomiej Bosek, Sebastian Czerwiński, Jarosław Grytczuk, Grzegorz Matecki, Wiktor Żelazny · Graphs and Combinatorics · 2013
An additive coloring of a graph G is an assignment of positive integers $${\{1,2,\ldots ,k\}}$$ to the vertices of G such that for every two adjacent vertices the sums of numbers assigned to their neighbors are different. The minimum number k for which there exists an additive coloring of G is denoted by $${\eta (G)}$$ . We prove that $${\eta (G) \, \leqslant \, 468}$$ for every planar graph G. This improves a previous bound $${\eta (G) \, \leqslant \, 5544}$$ due to Norin. The proof uses Combinatorial Nullstellensatz and the coloring number of planar hypergraphs. We also demonstrate that $${\eta (G) \, \leqslant \, 36}$$ for 3-colorable planar graphs, and $${\eta (G) \, \leqslant \, 4}$$ for every planar graph of girth at least 13. In a group theoretic version of the problem we show that for each $${r \, \geqslant \, 2}$$ there is an r-chromatic graph G r with no additive coloring by elements of any abelian group of order r.