Neighbor Distinguishing Edge Colorings Via the Combinatorial Nullstellensatz Revisited

作者：Przybylo Jakub^*; Wong Tsai Lien

来源：Journal of Graph Theory, 2015, 80(4): 299-312.

DOI：10.1002/jgt.21852

• neighbor distinguishing proper edge coloring
• neighbor sum distinguishing edge coloring
• adjacent strong chromatic index
• Combinatorial Nullstellensatz
• list edge coloring

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.

• 出版日期2015-12
• 单位中山大学