# zbMATH — the first resource for mathematics

Neighbor sum (set) distinguishing total choosability of $$d$$-degenerate graphs. (English) Zbl 1342.05052
Summary: Let $$G=(V,E)$$ be a graph with maximum degree $$\varDelta (G)$$ and $$\phi:V\cup E\to\{1,2,\dots,k\}$$ be a proper total coloring of the graph $$G$$. Let $$S(v)$$ denote the set of the color on vertex $$v$$ and the colors on the edges incident with $$v$$. Let $$f(v)$$ denote the sum of the color on vertex $$v$$ and the colors on the edges incident with $$v$$. The proper total coloring $$\phi$$ is called neighbor set distinguishing or adjacent vertex distinguishing if $$S(u)\neq S(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$$. Ding et al. proved in both problems $$k\geq\varDelta (G)+2d$$ is sufficient for $$d$$-degenerate graph $$G$$. In this paper, we improve this bound and prove that $$k\geq\varDelta (G)+d+1$$ is sufficient for $$d$$-degenerate graph $$G$$ with $$d\leq 8$$ and $$\varDelta (G)\geq 2d$$ or $$d\geq 9$$ and $$\varDelta (G)\geq\frac{5}{2}d-5$$. In fact, we prove these results in their list versions. As a consequence, we obtain an upper bound of the form $$\varDelta (G)+C$$ for some families of graphs, e.g. $$\varDelta (G)+6$$ for planar graphs with $$\varDelta (G)\geq 10$$. In particular, we therefore obtain that when $$\varDelta (G)\geq 4$$ two conjectures we mentioned above hold for 2-degenerate graphs in their list versions.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
Full Text:
##### References:
  Alon, N, Combinatorial nullstellensatz, Comb. Probab. Comput., 8, 7-29, (1999) · Zbl 0920.05026  Bondy, J., Murty, U.: Graph theory. Springer, London (2008) · Zbl 1134.05001  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 with maximum degree $$\varDelta$$, Discret. Appl. Math., 190, 34-41, (2015) · Zbl 1316.05041  Ding, L., Wang, G., Wu, J., Yu, J.: Neighbor sum (set) distinguishing total choosability via the Combinatorial Nullstellensatz. Sci. China. Math. 57(9), 1875-1882 · Zbl 1303.05058  Ding, L; Wang, G; Yan, G, Neighbor sum distinguishing total colorings via the combinatorial nullstellensatz, Sci. China Math., 57, 1875-1882, (2014) · Zbl 1303.05058  Dong, A; Wang, G, Neighbor sum distinguishing total coloring of graphs with bounded maximum average degree, Acta Math. Sin., 30, 703-709, (2014) · Zbl 1408.05061  Li, H; Ding, L; Liu, B; Wang, G, Neighbor sum distinguishing total colorings of planar graphs, J. Comb. Optim., 30, 675-685, (2015) · Zbl 1325.05083  Li, H; Liu, B; Wang, G, Neighbor sum distinguishing total colorings of $$K_{4}$$-minor free graphs, Front. Math. China, 8, 1351-1366, (2013) · Zbl 1306.05066  Przybyło, J, Neighbor distinguishing edge colorings via combinatorial nullstellensatz, SIAM J. Discrete Math., 27, 1313-1322, (2013) · Zbl 1290.05079  Pilśniak, M., Woźniak, M.: On the adjacent vertex distinguishing index by sums in total proper colorings. Graphs Comb. (2013). doi:10.1007/s00373-013-1399-4  Wang, G., Ding, L., Cheng X., Wu, J.: Improved bounds for neighbor sum (set) distinguishing choosability of planar graphs, Submitted  Wang, W; Huang, D, The adjacent vertex distinguishing total coloring of planar graphs, J. Comb. 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. China Ser. A, 39, 1462-1472, (2009)  Wang, Y; Wang, W, Adjacent vertex distinguishing total colorings of outerplanar graphs, J. Comb. Optim., 19, 123-133, (2010) · Zbl 1216.05039  Yao, J., Yu, X., Wang, G., Xu, C.: Neighbor sum distinguishing total coloring of 2-degenerate graph, Submitted · Zbl 1394.05037  Zhang, Z; Chen, X; Li, J; Yao, B; Lu, X; Wang, J, On adjacent-vertex-distinguishing total coloring of graphs, Sci. China 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.