Neighbor Distinguishing Edge Colorings Via the Combinatorial Nullstellensatz Revisited |
| |
Authors: | Jakub Przybyło Tsai‐Lien Wong |
| |
Affiliation: | 1. AGH UNIVERSITY OF SCIENCE AND TECHNOLOGY, KRAKOW, POLAND;2. DEPARTMENT OF APPLIED MATHEMATICS, NATIONAL SUN YAT‐SEN UNIVERSITY, KAOHSIUNG, TAIWAN |
| |
Abstract: | Consider a simple graph and its proper edge coloring c with the elements of the set . We say that c is neighbor set distinguishing (or adjacent strong) if for every edge , 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 . We prove that in both problems 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 as edge colors, and the same is true in list versions of the both concepts. In particular, we therefore obtain that lists of length ( in fact) are sufficient for planar graphs. |
| |
Keywords: | neighbor distinguishing proper edge coloring neighbor sum distinguishing edge coloring adjacent strong chromatic index Combinatorial Nullstellensatz list edge coloring 05C15 05C78 |
|
|