×

zbMATH — the first resource for mathematics

Neighbor sum distinguishing total chromatic number of 2-degenerate graphs. (English) Zbl 1401.05128
Summary: Let \(G = (V(G), E(G))\) be a graph and \(\phi\) be a proper total \(k\)-coloring of \(G\) by using the color set \(\{1, 2, \ldots, k \}\). For any \(v \in V(G)\), let \(f(v) = \sum_{u v \in E(G)} \phi(u v) + \phi(v)\). The coloring \(\phi\) is neighbor sum distinguishing, if \(f(u) \neq f(v)\) for each edge \(u v \in E(G)\). The neighbor sum distinguishing total chromatic number of \(G\), denoted by \(\chi_\varSigma^{\prime \prime}(G)\), is the smallest integer \(k\) such that \(G\) admits a \(k\)-neighbor sum distinguishing total coloring. In this paper, by using the famous Combinatorial Nullstellensatz, we determine \(\chi_\varSigma^{\prime \prime}(G)\) for any 2-degenerate graph \(G\) with \(\varDelta(G) \geq 6\).

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N., Combinatorial Nullstellensatz, Combin. Probab. Comput., 8, 7-29, (1999) · Zbl 0920.05026
[2] Bonamy, M.; Przybyło, J., On the neighbour sum distinguishing index of planar graphs, J. Graph Theory, (2014) · Zbl 1367.05066
[3] Bondy, J.; Murty, U., Graph Theory with Applications, (1976), North-Holland: North-Holland New York · Zbl 1226.05083
[4] Cheng, X.; Huang, D.; Wang, G.; Wu, J., Neighbor sum distinguishing total colorings of planar graphs with maximum degree \(\Delta\), Discrete Appl. Math., 190, 34-41, (2015) · Zbl 1316.05041
[5] Ding, L.; Wang, G.; Yan, G., Neighbor sum distinguishing total colorings via the Combinatorial Nullstellensatz, Sci. China Math., 57, 9, 1875-1882, (2014) · Zbl 1303.05058
[6] Ding, L.; Wang, G.; Wu, J.; Yu, J., Neighbor sum (set) distinguishing total choosability via the Combinatorial Nullstellensatz, Graphs Comb., 33, 4, 885-900, (2017) · Zbl 1371.05078
[7] Dong, A.; Wang, G., Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, Acta Math. Sinica, Engl. Ser. Mar., 30, 4, 703-709, (2014) · Zbl 1408.05061
[8] Li, H.; Liu, B.; Wang, G., Neighbor sum distinguishing total colorings of \(K_4\)-minor free graphs, Front. Math. China, 8, 6, 1351-1366, (2013) · Zbl 1306.05066
[9] Li, H.; Ding, L.; Liu, B.; Wang, G., Neighbor sum distinguishing total colorings of planar graphs, J. Comb. Optim., 30, 3, 675-688, (2015) · Zbl 1325.05083
[10] Pilśniak, M.; Woźniak, M., On the total-neighbor-distinguishing index by sums, Graphs Combin., 31, 3, 771-782, (2015) · Zbl 1312.05054
[11] Qu, C.; Wang, G.; Wu, J.; Yu, X., On the neighbor sum distinguishing total coloring of planar graphs, Theoret. Comput. Sci., 609, 162-170, (2016) · Zbl 1331.05084
[12] Song, H.; Xu, C., Neighbor sum distinguishing total chromatic number of \(K_4\)-minor free graph, Front. Math. China, 12, 4, 937-947, (2017) · Zbl 1371.05097
[13] Song, H.; Gong, X.; Pan, W.; Xu, C., Neighbor sum distinguishing total coloring of Halin graphs, J. Shandong Univ. Nat. Sci., 51, 4, 65-67, (2016) · Zbl 1363.05078
[14] Song, H.; Pan, W.; Gong, X.; Xu, C., A note on the neighbor sum distinguishing total coloring of planar graphs, Theoret. Comput. Sci., 640, 125-129, (2016) · Zbl 1345.05035
[15] Wang, G.; Ding, L.; Cheng, X.; Wu, J., Improved bounds for neighbor sum (set) distinguishing choosability of planar graphs, SIAM Discrete Math., (2015), submitted for publication
[16] Yao, J.; Yu, X.; Wang, G.; Xu, C., Neighbor sum (set) distinguishing total choosability of \(d\)-degenerate graphs, Graphs Comb., 32, 4, 1611-1620, (2016) · Zbl 1342.05052
[17] Yao, J.; Yu, X.; Wang, G.; Xu, C., Neighbor sum distinguishing total coloring of 2-degenerate graphs, J. Comb. Optim., 34, 1, 937-947, (2017)
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.