# zbMATH — the first resource for mathematics

Graphs with bounded maximum average degree and their neighbor sum distinguishing total-choice numbers. (English) Zbl 1441.05078
Summary: Let $$G$$ be a graph and $$\phi : V(G) \cup E(G) \rightarrow \{1,2, 3, \ldots, k \}$$ be a $$k$$-total coloring. Let $$w(v)$$ denote the sum of color on a vertex $$v$$ and colors assigned to edges incident to $$v$$. If $$w(u) \neq w(v)$$ whenever $$u v \in E(G)$$, then $$\phi$$ is called a neighbor sum distinguishing total coloring. The smallest integer $$k$$ such that $$G$$ has a neighbor sum distinguishing $$k$$-total coloring is denoted by $$\mathrm{tndi}_{\Sigma}(G)$$. A. J. Dong and G. H. Wang [Acta Math. Sin., Engl. Ser. 30, No. 4, 703–709 (2014; Zbl 1408.05061)] obtained the results about $$\mathrm{tndi}_{\Sigma}(G)$$ depending on the value of maximum average degree. A $$k$$-assignment $$L$$ of $$G$$ is a list assignment $$L$$ of integers to vertices and edges with $$\left|L(v)\right| = k$$ for each vertex $$v$$ and $$\left|L(e)\right| = k$$ for each edge $$e$$. A total-$$L$$-coloring is a total coloring $$\phi$$ of $$G$$ such that $$\phi(v) \in L(v)$$ whenever $$v \in V(G)$$ and $$\phi(e) \in L(e)$$ whenever $$e \in E(G)$$. We state that $$G$$ has a neighbor sum distinguishing total-$$L$$-coloring if $$G$$ has a total-$$L$$-coloring such that $$w(u) \neq w(v)$$ for all $$u v \in E(G)$$. The smallest integer $$k$$ such that $$G$$ has a neighbor sum distinguishing total-$$L$$-coloring for every $$k$$-assignment $$L$$ is denoted by $$\mathrm{Ch}_{\Sigma}^{\prime\prime}(G)$$. In this paper, we strengthen results by Dong and Wang [loc. cit.] by giving analogous results for $$\mathrm{Ch}_{\Sigma}^{\prime\prime}(G)$$.
Reviewer: Reviewer (Berlin)
##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C07 Vertex degrees
##### Keywords:
total-$$L$$-coloring; $$k$$-total coloring
Full Text:
##### References:
  Zhang, Z.; Chen, X. E.; Li, J.; Yao, B.; Lu, X.; Wang, J., On adjacent-vertex-distinguishing total coloring of graphs, Science China Mathematics, 48, 3, 289-299, (2005) · Zbl 1080.05036  Chen, X., On the adjacent vertex distinguishing total coloring numbers of graphs with $$\Delta = 3$$, Discrete Mathematics, 308, 17, 4003-4007, (2008) · Zbl 1203.05052  Wang, W.; Huang, D., The adjacent vertex distinguishing total coloring of planar graphs, Journal of Combinatorial Optimization, 27, 2, 379-396, (2014) · Zbl 1319.90076  Wang, W.; Wang, P., On adjacent-vertex-distinguishing total coloring of K4-minor free graphs, Sci. China Ser. A, 39, 12, 1462-1472, (2009)  Pilśniak, M.; Woźniak, M., On the total-neighbor-distinguishing index by sums, Graphs and Combinatorics, 31, 3, 771-782, (2015) · Zbl 1312.05054  Li, H.; Liu, B.; Wang, G., Neighbor sum distinguishing total colorings of K_4-minor free graphs, Frontiers of Mathematics in China, 8, 6, 1351-1366, (2013) · Zbl 1306.05066  Li, H.; Ding, L.; Liu, B.; Wang, G., Neighbor sum distinguishing total colorings of planar graphs, Journal of Combinatorial Optimization, 30, 3, 675-688, (2015) · Zbl 1325.05083  Wang, J. H.; Ma, Q. L.; Han, X., Neighbor sum distinguishing total colorings of triangle free planar graphs, Acta Mathematica Sinica, 31, 2, 216-224, (2015) · Zbl 1317.05065  Cheng, X.; Huang, D.; Wang, G.; Wu, J., Neighbor sum distinguishing total colorings of planar graphs with maximum degree $$\Delta$$, Discrete Applied Mathematics: The Journal of Combinatorial Algorithms, Informatics and Computational Sciences, 190-191, 34-41, (2015) · Zbl 1316.05041  Qu, C.; Wang, G.; Wu, J.; Yu, X., On the neighbor sum distinguishing total coloring of planar graphs, Theoretical Computer Science, 609, part 1, 162-170, (2016) · Zbl 1331.05084  Song, H. J.; Pan, W. H.; Gong, X. N.; Xu, C. Q., A note on the neighbor sum distinguishing total coloring of planar graphs, Theoretical Computer Science, 640, 125-129, (2016) · Zbl 1345.05035  Dong, A. J.; Wang, G. H., Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, Acta Mathematica Sinica, 30, 4, 703-709, (2014) · Zbl 1408.05061  Vizing, V. G., Vertex colorings with given colors  Erdös, P.; Rubin, A. L.; Taylor, H., Choosability in graphs, In Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, Arcata, Congr. Num.  Qu, C.; Wang, G.; Yan, G.; Yu, X., Neighbor sum distinguishing total choosability of planar graphs, Journal of Combinatorial Optimization, 32, 3, 906-916, (2016) · Zbl 1348.05082  Yao, J.; Yu, X.; Wang, G.; Xu, C., Neighbor sum (set) distinguishing total choosability of d-degenerate graphs, Graphs and Combinatorics, 32, 4, 1611-1620, (2016) · Zbl 1342.05052  Wang, J.; Cai, J.; Ma, Q., Neighbor sum distinguishing total choosability of planar graphs without 4-cycles, Discrete Applied Mathematics: The Journal of Combinatorial Algorithms, Informatics and Computational Sciences, 206, 215-219, (2016) · Zbl 1335.05051
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.