# zbMATH — the first resource for mathematics

Neighbor sum (set) distinguishing total choosability via the combinatorial Nullstellensatz. (English) Zbl 1371.05078
Summary: Let $$G=(V,E)$$ be a graph and $$\phi :V\cup E\rightarrow \{1,2,\dots,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)\neq C(v)$$ for each edge $$uv\in E(G)$$. We say that $$\phi$$ is neighbor sum distinguishing if $$f(u)\neq 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\geq \varDelta (G)+3$$. In this paper, by using the famous Combinatorial Nullstellensatz, we prove that in both problems $$k\geq \varDelta (G)+2\mathrm{col}(G)-2$$ is sufficient, moreover we prove that if $$G$$ is not a forest and $$\varDelta \geq 4$$, then $$k\geq \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 \geq 4$$ two conjectures we mentioned above hold for 2-degenerate graphs (with coloring number at most 3) in their list versions.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
Full Text:
##### References:
  Alon, N, Combinatorial nullstellensatz, Combin. Probab. Comput., 8, 7-29, (1999) · Zbl 0920.05026  Bondy, J., Murty, U.: Graph Theory with Applications. North-Holland, New York (1976) · Zbl 1226.05083  Chartrand, G; Jacobson, M; Lehel, J; Oellermann, O; Ruiz, S; Saba, F, Irregular networks, Congr. Numer., 64, 197-210, (1988) · Zbl 0671.05060  Chen, X, On the adjacent vertex distinguishing total coloring numbers of graphs with $$\varDelta = 3$$, Discrete Math., 308, 4003-4007, (2008) · Zbl 1203.05052  Cheng, X; Wu, J; Huang, D; Wang, G, Neighbor sum distinguishing total colorings of planar graphs with maximum degree $$\varDelta$$, Discrete Appl. Math., 190, 34-41, (2015) · Zbl 1316.05041  Ding, L; Wang, G; Yan, G, Neighbor sum distinguishing total colorings via the combinatorial nullstellensatz, Sci. Sin. Math., 57, 1875-1882, (2014) · Zbl 1303.05058  Dong, A; Wang, G, Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, Acta Math. Sin., 30, 703-709, (2014) · Zbl 1408.05061  Huang, D; Wang, W, Adjacent vertex distinguishing total coloring of planar graphs with large maximum degree, (in Chinese), Sci. Sin. Math., 42, 151-164, (2012)  Huang, P; Wong, T; Zhu, X, Weighted-1-antimagic graphs of prime power order, Discrete Math., 312, 2162-2169, (2012) · Zbl 1244.05186  Kalkowski, M; Karoński, M; Pfender, F, Vertex-coloring edge-weightings: towards the 1-2-3-conjecture, J. Combin. Theory Ser. B, 100, 347-349, (2010) · Zbl 1209.05087  Karoński, M; Łuczak, T; Thomason, A, Edge weights and vertex colours, J. Combin. Theory Ser. B, 91, 151-157, (2004) · Zbl 1042.05045  Li, H; Ding, L; Liu, B; Wang, G, Neighbor sum distinguishing total colorings of planar graphs, J. Combin. Optim., 30, 675-688, (2015) · Zbl 1325.05083  Li, H; Liu, B; Wang, G, Neighor sum distinguishing total colorings of $$K_4$$-minor free graphs, Front. Math. China, 8, 1351-1366, (2013) · Zbl 1306.05066  Pilśniak, M; Woźniak, M, On the total-neighbor-distinguishing index by sums, Graph Combin., 31, 771-782, (2015) · Zbl 1312.05054  Przybyło, J, Neighbour distinguishing edge colorings via the combinatorial nullstellensatz, SIAM J. Discrete Math., 27, 1313-1322, (2013) · Zbl 1290.05079  Przybyło, J, Irregularity strength of regular graphs, Electron. J. Combin, 15, r82, (2008) · Zbl 1163.05329  Przybyło, J, Linear bound on the irregularity strength and the total vertex irregularity strength of graphs, SIAM J. Discrete Math., 23, 511-516, (2009) · Zbl 1216.05135  Przybyło, J; Woźniak, M, Total weight choosability of graphs, Electron. J. Combin., 18, p112, (2011) · Zbl 1217.05202  Przybyło, J; Woźniak, M, On a 1,2 conjecture, Discrete Math. Theor. Comput. Sci., 12, 101-108, (2010) · Zbl 1250.05093  Seamone, B.: The 1-2-3 conjecture and related problems: a survey. arXiv:1211.5122 · Zbl 1302.05059  Wang, W; Huang, D, The adjacent vertex distinguishing total coloring of planar graphs, J. Combin. Optim., 27, 379-396, (2014) · Zbl 1319.90076  Wang, W; Wang, P, On adjacent-vertex-distinguishing total coloring of $$K_4$$-minor free graphs, Sci. Sin. Math. Ser. A, 39, 1462-1472, (2009)  Wang, Y; Wang, W, Adjacent vertex distinguishing total colorings of outerplanar graphs, J. Combin. Optim., 19, 123-133, (2010) · Zbl 1216.05039  Wong, T; Zhu, X, Total weight choosability of graphs, J. Graph Theory, 66, 198-212, (2011) · Zbl 1228.05161  Wong, T; Zhu, X, Antimagic labelling of vertex weighted graphs, J. Graph Theory, 3, 348-359, (2012) · Zbl 1244.05192  Zhang, Z; Chen, X; Li, J; Yao, B; Lu, X; Wang, J, On adjacent-vertex-distinguishing total coloring of graphs, Sci. Sin. Math. Ser. A, 48, 289-299, (2005) · Zbl 1080.05036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.