Neighbor Distinguishing Edge Colorings via the Combinatorial Nullstellensatz
Jakub Przybyło · SIAM Journal on Discrete Mathematics · 2013
Consider a simple graph $G=(V,E)$ and its proper edge coloring $c$ with the elements of the set $\{1,2,\ldots,k\}$ (or any other $k$-element set of real numbers). We say that $c$ is neighbor sum distinguishing if $\sum_{w\in N_G(v)}c(wv) eq \sum_{w\in N_G(u)}c(wu)$ for every edge $uv\in E$. We show that such a coloring exists for any graph $G$ containing no isolated edges if $k\geq 2\Delta(G)+{\rm col}(G)-1$. The proof of this fact is based on iterative applications of the Combinatorial Nullstellensatz. As a consequence, the same number of colors is also sufficient in the well-known corresponding problem, where instead of the sums, we wish to distinguish the sets of colors met by adjacent vertices. In fact we consider list versions of both concepts and prove our assertion in this more general setting.