×

zbMATH — the first resource for mathematics

Neighbor sum distinguishing total coloring of IC-planar graphs. (English) Zbl 1445.05043
The authors consider the problem of neighbor sum distinguishing total coloring of IC-planar graphs. A proper total-\(k\)-coloring of a graph \(G\) is a mapping \(c: V(G)\cup E(G) \rightarrow \{1, 2, \ldots, k\}\) such that any two adjacent elements in \(V(G) \cup E(G)\) receive different colors. Let \(\sum_c(u)\) denote the sum of the color of a vertex \(v\) and the colors of all edges incident with \(v\). If for each edge \(uv \in E(G)\), \(\sum_c(u) \ne\sum_c (v)\), then such a proper total-\(k\)-coloring is called a \(k\)-neighbor sum distinguishing total coloring, denoted by tnsd-\(k\)-coloring, for short. The least number \(k\) needed for such a coloring of \(G\), denoted by \(\chi^{\prime\prime}_{\Sigma}(G)\), is the neighbor sum distinguishing total chromatic number. The problem is very well known in the literature. There is a known conjecture, posed by M. Pilśniak and M. Woźniak [Graphs Comb. 31, No. 3, 771–782 (2015; Zbl 1312.05054)], that \(\chi^{\prime\prime}_{\Sigma}(G)\leq \Delta(G)+3\) for any graph \(G\). Also some other bounds on \(\chi^{\prime\prime}_{\Sigma}(G)\)are known proved for general or particular classes of graphs.
This paper contributes a lot to the knowledge in the area of neighbor sum distinguishing total coloring by proving that \(\chi^{\prime\prime}_{\Sigma}(G)\leq \Delta(G)+2\) for IC-planar graphs without 2-vertex incident with crossed edge and with \(\Delta(G)\geq 14\). The proof of the result is very interesting and carried with great care.
I find the paper very valuable.
MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C07 Vertex degrees
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alberson, M. O., Chromatic number, independent ratio, and crossing number, Ars Math. Contemp., 1, 1-6 (2008) · Zbl 1181.05032
[2] Alon, N., Combinatorial Nullstellensatz, Combin. Probab. Comput., 8, 7-29 (1999) · Zbl 0920.05026
[3] Bondy, J. A.; Murty, U. S.R., 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. Sin. Math., 57, 9, 1875-1882 (2014) · Zbl 1303.05058
[6] Dong, A.; Wang, G., Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, Acta Math. Sinica, 30, 4, 703-709 (2014) · Zbl 1408.05061
[7] Li, H.; Ding, L.; Liu, B.; Wang, G., Neighbor sum distinguishing total colorings of planar graphs, J. Comb. Optim., 30, 3, 675-688 (2013) · Zbl 1325.05083
[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] Loeb, S.; Tang, Y., Asymptotically optimal neighbor sum distinguishing total colorings of graphs, Discrete Math., 340, 2, 58-62 (2017) · Zbl 1351.05083
[10] Lu, Y.; Han, M. M.; Luo, R., Neighbor sum distinguishing total coloring and list neighbor sum distinguishing total coloring, Discrete Appl. Math., 237, 109-115 (2018) · Zbl 1380.05076
[11] Pilśniak, M.; Woźniak, M., On the total-neighbor-distinguishing index by sums, Graphs Combin., 31, 1-12 (2013)
[12] 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
[13] Song, W.; Miao, L., Neighbor sum distinguishing total choosability of IC-planar graphs, Discuss. Math. Graph Theory, 40, 331-344 (2020) · Zbl 1430.05023
[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] Xu, R. Y.; Wu, J.; Xu, J., Neighbor sum distinguishing total coloring of graphs embedded in surfaces of nonnegative Euler characteristic, J. Comb. Optim., 31, 1430-1442 (2016) · Zbl 1339.05149
[16] Yang, D.; Yu, X.; Sun, L.; 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
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.