Lucky labelings of graphs

Suppose the vertices of a graph G were labeled arbitrarily by positive integers, and let S(v) denote the sum of labels over all neighbors of vertex v. A labeling is lucky if the function S is a proper coloring of G, that is, if we have S(u)≠S(v) whenever u and v are adjacent. The least integer k for which a graph G has a lucky labeling from the set {1,2,…,k} is the lucky number of G, denoted by η(G).Using algebraic methods we prove that η(G)⩽k+1 for every bipartite graph G whose edges can be oriented so that the maximum out-degree of a vertex is at most k. In particular, we get that η(T)⩽2 for every tree T, and η(G)⩽3 for every bipartite planar graph G. By another technique we get a bound for the lucky number in terms of the acyclic chromatic number. This gives in particular that for every planar graph G. Nevertheless we offer a provocative conjecture that η(G)⩽χ(G) for every graph G.