Premium
Neighbor Distinguishing Edge Colorings Via the Combinatorial Nullstellensatz Revisited
Author(s) -
Przybyło Jakub,
Wong TsaiLien
Publication year - 2015
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21852
Subject(s) - combinatorics , mathematics , graph , simple (philosophy) , planar graph , enhanced data rates for gsm evolution , set (abstract data type) , edge coloring , simple graph , discrete mathematics , computer science , line graph , graph power , artificial intelligence , philosophy , epistemology , programming language
Abstract 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.