×

Neighbor sum distinguishing total chromatic number of planar graphs with maximum degree 10. (English) Zbl 1426.05051

Summary: Given a simple graph \(G\), a proper total-\(k\)-coloring \(\phi : V(G) \cup E(G) \rightarrow \{1, 2, \ldots, k \}\) is called neighbor sum distinguishing if \(S_{\phi}(u) \neq S_{\phi}(v)\) for any two adjacent vertices \(u,v \in V(G)\), where \(S_{\phi}(u)\) is the sum of the color of \(u\) and the colors of the edges incident with \(u\). It has been conjectured by M. Pilśniak and M. Woźniak [Graphs Comb. 31, No. 3, 771–782 (2015; Zbl 1312.05054)] that \(\mathop{\Delta}(G) + 3\) colors enable the existence of a neighbor sum distinguishing total coloring. The conjecture is confirmed for any graph with maximum degree at most 3 and for planar graph with maximum degree at least 11. We prove that the conjecture holds for any planar graph \(G\) with \(\mathop{\Delta}(G) = 10\). Moreover, for any planar graph \(G\) with \(\mathop{\Delta}(G) \geq 11, \mathop{\Delta}(G) + 2\) colors guarantee such a total coloring, and the upper bound \(\mathop{\Delta}(G) + 2\) is tight.

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory

Citations:

Zbl 1312.05054
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 with Applications (1976), North-Holland: North-Holland New York · Zbl 1226.05083
[3] Chartrand, G., How to define an irregular graph, Coll. Math. J., 19, 1, 36-42 (1998) · Zbl 0995.05516
[4] Cheng, X.; Huang, D.; Wang, G.; Wu, J., Neighbor sum distinguishing total colorings of planar graphs with maximum degree \(δ\), Discret. Appl. Math., 190-191, 34-41 (2015) · Zbl 1316.05041
[5] Coker, T.; Johannson, K., The adjacent vertex distinguishing total chromatic number, Discret. Math., 312, 741-2750 (2012) · Zbl 1245.05042
[6] 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
[7] Ding, L.; Wang, G.; Wu, J.; Yu, J., Neighbor sum (set) distinguishing total choosability via the Combinatorial Nullstellensatz, Graphs Combin. (2017) · Zbl 1371.05078
[8] Dong, A.; Wang, G., Neighbor sum distinguishing coloring of some graphs, Discret. Math. Algorithms Appl., 04, 4 (2013)
[9] Dong, A.; Wang, G., Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, Acta Math. Sin. Engl., 30, 4, 703-709 (2014) · Zbl 1408.05061
[10] Li, H.; Ding, L.; Liu, B., Neighbor sum distinguishing total colorings of planar graphs, J. Combin. Optim., 30, 3, 1-14 (2013)
[11] Li, H.; Liu, B.; Wang, G., Neighbor sum distinguishing total colorings of \(K4\)-minor free graphs, Front. Math. China, 8, 6, 1351-1366 (2013) · Zbl 1306.05066
[12] Loeb, S.; Tang, Y., Asymptotically optimal neighbor sum distinguishing total colorings of graphs, Discret. Math., 340, 2, 58-62 (2017) · Zbl 1351.05083
[13] Majerski, P.; Przybyło, J., On the irregular strength of dense graphs, SIAM J. Discret. Math., 28, 1, 197-205 (2014) · Zbl 1293.05341
[14] Pilśniak, M.; Woźniak, M., On the total-neighbor-distinguishing index by sums, Graphs Combin., 31, 3, 771-782 (2015) · Zbl 1312.05054
[15] Przybyło, J., Irregularity stength of regular graphs, Electron. J. Combin., 15, 1, 1350-1370 (2008) · Zbl 1163.05329
[16] Przybyło, J., Neighbour sum distinguishing total colourings via the Combinatorial Nullstellensatz, Discrete Applied Mathematics, Discret. Appl. Math., 202, 163-173 (2016) · Zbl 1330.05074
[17] Qu, C.; Wang, W.; Yan, G.; Yu, X., Neighbor sum distinguishing total choosability of planar graphs, J. Combin. Optim., 32, 3, 906-916 (2016) · Zbl 1348.05082
[18] Qu, C.; Wang, W.; Wu, J.; Yu, X., On the neighbor sum distinguishing total coloring of planar graphs, Theor. Comput. Sci., 609, 1, 162-170 (2016) · Zbl 1331.05084
[19] Song, H.; Pan, W.; Gong, X.; Xu, C., A note on neighbor sum distinguishing total coloring of planar graphs, Theor. Comput. Sci., 640, C, 125-129 (2016) · Zbl 1345.05035
[20] Wang, W.; Huang, D., The adjacent vertex distinguishing total coloring of planar graphs, J. Combin. Optim., 27, 2, 379-396 (2014) · Zbl 1319.90076
[21] 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, 3, 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.