Additive list coloring of planar graphs with given girth
Axel Brandt, Sogol Jahanbekam, Jennifer White · Discussiones Mathematicae Graph Theory · 2018
An additive coloring of a graph G is a labeling of the vertices of G from {1, 2, . . . , k} such that two adjacent vertices have distinct sums of labels on their neighbors. The least integer k for which a graph G has an additive coloring is called the additive coloring number of G, denoted (G). Additive coloring is also studied under the names lucky labeling and open distinguishing. In this paper, we improve the current bounds on the additive coloring number for particular classes of graphs by proving results for a list version of additive coloring. We apply the discharging method and the Combinatorial Nullstellensatz to show that every planar graph G with girth at least 5 has (G) 19, and for girth at least 6, 7, and 26, (G) is at most 9, 8, and 3, respectively. In 2009, Czerwiski, Grytczuk, and elazny that (G) (G), where (G) is the chromatic number of G. Our result for