×

zbMATH — the first resource for mathematics

Neighbor sum distinguishing total choosability of cubic graphs. (English) Zbl 07311129
Summary: Let \(G=(V, E)\) be a graph and \({\mathbb{R}}\) be the set of real numbers. For a \(k\)-list total assignment \(L\) of \(G\) that assigns to each member \(z\in V\cup E\) a set \(L_z\) of \(k\) real numbers, a neighbor sum distinguishing (NSD) total \(L\)-coloring of \(G\) is a mapping \(\phi :V\cup E \rightarrow{\mathbb{R}}\) such that every member \(z\in V\cup E\) receives a color of \(L_z\), every pair of adjacent or incident members in \(V\cup E\) receive different colors, and \(\sum_{z\in E_G(u)\cup \{u\}}\phi (z)\ne \sum_{z\in E_G(v)\cup \{v\}}\phi (z)\) for each edge \(uv\in E\), where \(E_G(v)\) is the set of edges incident with \(v\) in \(G\). M. Pilśniak and M. Woźniak [Graphs Comb. 31, No. 3, 771–782 (2015; Zbl 1312.05054)] posed the conjecture that every graph \(G\) with maximum degree \(\Delta\) has an NSD total \(L\)-coloring with \(L_z=\{1,2,\dots , \Delta +3\}\) for any \(z\in V\cup E\), and confirmed the conjecture for all cubic graphs. In this paper, we extend their result by proving that every cubic graph has an NSD total \(L\)-coloring for any 6-list total assignment \(L\).
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] Bondy, J.A., Murty, U.S.R.: Graph theory. In: GTM, vol. 244. Springer, Berlin (2008)
[3] Ding, L.; Wang, G.; Wu, J.; Yu, J., Neighbor sum (set) distinguishing total choosability via the Combinatorial Nullstellensatz, Graphs Combin., 33, 885-900 (2017) · Zbl 1371.05078
[4] Han, M.; Lu, Y.; Luo, R.; Miao, Z., Neighbor sum distinguishing total coloring of graphs with bounded treewidth, J. Combin. Optim., 36, 23-34 (2018) · Zbl 1396.05039
[5] Li, H.; Liu, B.; Wang, G., Neighbor sum distinguishing total coloring of \(K_4\)-minor-free graphs, Front. Math. China, 8, 1351-1366 (2013) · Zbl 1306.05066
[6] Lu, Y.; Xu, C.; Miao, Z., Neighbor sum distinguishing list total coloring of subcubic graphs, J. Combin. Optim., 35, 778-793 (2018) · Zbl 1387.05094
[7] Pilśniak, M.; Woźniak, M., On the total-neighbor-distinguishing index by sums, Graphs Combin., 31, 771-782 (2015) · Zbl 1312.05054
[8] Qu, C.; Ding, L.; Wang, G.; Yan, G., Neighbor distinguishing total choice number of sparse graphs via the Combinatorial Nullstellensatz, Acta Math. Sin. (Engl. Ser.), 32, 537-548 (2016) · Zbl 1336.05046
[9] Qu, C.; Wang, G.; Yan, G.; Yu, X., Neighbor sum distinguishing total choosability of planar graphs, J. Combin. Optim., 32, 906-916 (2016) · Zbl 1348.05082
[10] Song, W.; Miao, L.; Li, J.; Zhao, Y.; Pang, J., Neighbor sum distinguishing total coloring of sparse IC-planar graphs, Discrete Appl. Math., 239, 183-192 (2018) · Zbl 1382.05019
[11] Wang, J.; Cai, J.; Ma, Q., Neighbor sum distinguishing total choosability of planar graphs without 4-cycles, Discrete Appl. Math., 206, 215-219 (2016) · Zbl 1335.05051
[12] Wang, J.; Cai, J.; Qiu, B., Neighbor sum distinguishing total choosability of planar graphs without adjacent triangles, Theor. Comput. Sci., 661, 1-7 (2017) · Zbl 1357.05027
[13] Xu, C.; Ge, S.; Li, J., Neighbor sum distinguishing total chromatic number of 2-degenerate graphs, Discrete Appl. Math., 251, 349-352 (2018) · Zbl 1401.05128
[14] Xu, C.; Li, J.; Ge, S., Neighbor sum distinguishing total chromatic number of planar graphs, Appl. Math. Comput., 332, 189-196 (2018) · Zbl 1427.05093
[15] Yang, D.; Sun, L.; Yu, X.; Wu, J.; Zhou, S., Neighbor sum distinguishing total chromatic number of planar graphs with maximum degree 10, Appl. Math. Comput., 314, 456-468 (2017) · Zbl 1426.05051
[16] Yao, J.; Yu, X.; Wang, G.; Xu, C., Neighbor sum (set) distinguishing total choosability of \(d\)-degenerate graphs, Graphs Comb., 32, 1611-1620 (2016) · Zbl 1342.05052
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.