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 u v ∈ E , 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.