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

Let $$G=(V,E)$$ be a graph and $$\phi :V\cup E\rightarrow \{1,2,\ldots ,k\}$$ 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 $$\phi $$ is called neighbor set distinguishing or adjacent vertex distinguishing if $$C(u)\ne C(v)$$ for each edge $$uv\in E(G)$$ . We say that $$\phi $$ is neighbor sum distinguishing if $$f(u)\ne f(v)$$ for each edge $$uv\in E(G)$$ . In both problems the challenging conjectures presume that such colorings exist for any graph G if $$k\ge \varDelta (G)+3$$ . In this paper, by using the famous Combinatorial Nullstellensatz, we prove that in both problems $$k\ge \varDelta (G)+2\mathrm{col}(G)-2$$ is sufficient, moreover we prove that if G is not a forest and $$\varDelta \ge 4$$ , then $$k\ge \varDelta (G)+2\mathrm{col}(G)-3$$ is sufficient, where $$\mathrm{col}(G)$$ 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 $$\varDelta (G)+C$$ for some families of graphs, e.g. $$\varDelta +9$$ for planar graphs. In particular, we therefore obtain that when $$\varDelta \ge 4$$ two conjectures we mentioned above hold for 2-degenerate graphs (with coloring number at most 3) in their list versions. [ABSTRACT FROM AUTHOR]