Neighbor Distinguishing Edge Colorings Via the Combinatorial Nullstellensatz Revisited

Consider a simple graph G=(V,E) and its proper edge coloring c with the elements of the set {1,...,k}. We say that c is neighbor set distinguishing (or adjacent strong) if for every edge uvE, the set of colors incident with u is distinct from the set of colors incident with v. Let us then consider a stronger requirement and suppose we wish to distinguishing adjacent vertices by sums of their incident colors. In both problems the challenging conjectures presume that such colorings exist for any graph G containing no isolated edges if only k(G)+2. We prove that in both problems k=(G)+3 col (G)-4 is sufficient. The proof is based on the Combinatorial Nullstellensatz, applied in the sum environment. In fact the identical bound also holds if we use any set of k real numbers instead of {1,...,k} as edge colors, and the same is true in list versions of the both concepts. In particular, we therefore obtain that lists of length (G)+14 ((G)+13 in fact) are sufficient for planar graphs. (C) 2014 Wiley Periodicals, Inc.