×

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)\).
MSC:
05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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
[2] 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
[3] 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
[4] Wang, W.; Wang, P., On adjacent-vertex-distinguishing total coloring of K4-minor free graphs, Sci. China Ser. A, 39, 12, 1462-1472, (2009)
[5] 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
[6] 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
[7] 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
[8] 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
[9] 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
[10] 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
[11] 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
[12] 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
[13] Vizing, V. G., Vertex colorings with given colors
[14] 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.
[15] 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
[16] 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
[17] 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.