Lucky Choice Number of Planar Graphs with Given Girth
Axel Brandt, Jennifer Diemunsch, Sogol Jahanbekam · San Jose State University Scholar Works (San Jose State University) · 2015
Suppose the vertices of a graph G are labeled with real numbers.For each vertex v ∈ G, let S(v) denote the sum of the labels of all vertices adjacent to v. A labeling is called lucky if S(u) = S(v) for every pair u and v of adjacent vertices in G.The least integer k for which a graph G has a lucky labeling from {1, 2, . . ., k} is called the lucky number of the graph, denoted η(G).In 2009, Czerwiński, Grytczuk, and Żelazny [6] conjectured that η(G) ≤ χ(G), where χ(G) is the chromatic number of G.In this paper, we improve the current bounds for particular classes of graphs with a strengthening of the results through a list lucky labeling.We apply the discharging method and the Combinatorial Nullstellensatz to show that for a planar graph G of girth at least 26, η(G) ≤ 3.This proves the conjecture for non-bipartite planar graphs of girth at least 26.We also show that for girth at least 7, 6, and 5, η(G) is at most 8, 9, and 19, respectively.