zbMATH — the first resource for mathematics

Neighbor distinguishing edge colorings via the combinatorial Nullstellensatz. (English) Zbl 1290.05079
Author’s abstract: 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) \neq \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) + \text{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.

05C15 Coloring of graphs and hypergraphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
Full Text: DOI