Neighbor Sum (Set) Distinguishing Total Choosability Via the Combinatorial Nullstellensatz

Let be a graph and be a total coloring of G. Let C(v) denote the set of the color of vertex v and the colors of the edges incident with v. Let f(v) denote the sum of the color of vertex v and the colors of the edges incident with v. The total coloring is called neighbor set distinguishing or adjacent vertex distinguishing if for each edge . We say that is neighbor sum distinguishing if for each edge . In both problems the challenging conjectures presume that such colorings exist for any graph G if . In this paper, by using the famous Combinatorial Nullstellensatz, we prove that in both problems is sufficient, moreover we prove that if G is not a forest and , then is sufficient, where is the coloring number of G. In fact we prove these results in their list versions, which improve the previous results. As a consequence, we obtain an upper bound of the form for some families of graphs, e.g. for planar graphs. In particular, we therefore obtain that when two conjectures we mentioned above hold for 2-degenerate graphs (with coloring number at most 3) in their list versions.