An additive coloring of a graph G is an assignment of positive integers $${\{1,2,\ldots ,k\}}$$ { 1 , 2 , ? , 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)}$$ ? ( G ) . We prove that $${\eta (G) \, \leqslant \, 468}$$ ? ( G ) ? 468 for every planar graph G. This improves a previous bound $${\eta (G) \, \leqslant \, 5544}$$ ? ( G ) ? 5544 due to Norin. The proof uses Combinatorial Nullstellensatz and the coloring number of planar hypergraphs. We also demonstrate that $${\eta (G) \, \leqslant \, 36}$$ ? ( G ) ? 36 for 3-colorable planar graphs, and $${\eta (G) \, \leqslant \, 4}$$ ? ( G ) ? 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}$$ r ? 2 there is an r-chromatic graph G r with no additive coloring by elements of any abelian group of order r.
['Tomasz Bartnicki', 'Bartłomiej Bosek', 'Sebastian Czerwiński', 'Jarosław Grytczuk', 'Grzegorz Matecki', 'Wiktor Żelazny']
Additive Coloring of Planar Graphs