Additive Coloring of Planar Graphs

作者：Bartnicki Tomasz; Bosek Bartlomiej; Czerwinski Sebastian; Grytczuk Jaroslaw^*; Matecki Grzegorz; Zelazny Wiktor

来源：Graphs and Combinatorics, 2014, 30(5): 1087-1098.

DOI：10.1007/s00373-013-1331-y

• Additive coloring
• Planar graphs

An additive coloring of a graph G is an assignment of positive integers 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 . We prove that for every planar graph G. This improves a previous bound due to Norin. The proof uses Combinatorial Nullstellensatz and the coloring number of planar hypergraphs. We also demonstrate that for 3-colorable planar graphs, and for every planar graph of girth at least 13. In a group theoretic version of the problem we show that for each there is an r-chromatic graph G (r) with no additive coloring by elements of any abelian group of order r.

• 出版日期2014-9