×

zbMATH — the first resource for mathematics

Neighbor sum distinguishing total colorings of IC-planar graphs with maximum degree 13. (English) Zbl 1434.05057
Summary: A graph is IC-planar if it admits a drawing on the plane with at most one crossing per edge, such that two pairs of crossing edges share no common end vertex. For a given graph \(G\), a proper total coloring \(\phi:V(G)\cup E(G)\rightarrow\{1,2,\dots,k\}\) is called neighbor sum distinguishing if \(f_{\phi }(u)\ne f_{\phi }(v)\) for each \(uv\in E(G)\), where \(f_{\phi }(u)\) is the sum of the color of \(u\) and the colors of the edges incident with \(u\). The smallest integer \(k\) in such a coloring of \(G\) is the neighbor sum distinguishing total chromatic number, denoted by \(\chi''_{\Sigma}(G)\). M. Pilśniak and M. Woźniak [Graphs Comb. 31, No. 3, 771–782 (2015; Zbl 1312.05054)] conjectured \(\chi''_{\Sigma}(G)\leq\Delta (G)+3\) for any simple graph with maximum degree \(\Delta (G)\). This conjecture was confirmed for IC-planar graph with maximum degree at least 14. In this paper, by using the discharging method, we prove that this conjecture holds for any IC-planar graph \(G\) with \(\Delta (G)=13\).
MSC:
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albertson, Mo, Chromatic number, independence ratio, and crossing number, Ars Math Contemp, 1, 1-6 (2008) · Zbl 1181.05032
[2] Alon, N., Combinatorial nullstellensatz, Comb Probab Comput, 8, 7-29 (1999) · Zbl 0920.05026
[3] Bondy, Ja; Murty, Usr, Graph theory with applications (1976), New York: North-Holland, New York
[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, 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 Combin, 33, 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 Sin (Engl Ser), 30, 703-709 (2014) · Zbl 1408.05061
[8] Li, H.; Ding, L.; Liu, B.; Wang, G., Neighbor sum distinguishing total coloring of planar graphs, J Comb Optim, 30, 3, 675-688 (2015) · Zbl 1325.05083
[9] 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
[10] Loeb, S.; Tang, Y., Asymptotically optimal neighbor sum distinguishing total colorings of graphs, Discrete Math, 340, 2, 58-62 (2017) · Zbl 1351.05083
[11] Lu, Y.; Han, 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
[12] Pilśniak, M.; Woźniak, M., On the total-neighbor-distinguishing index by sums, Graphs Comb, 31, 3, 771-782 (2015) · Zbl 1312.05054
[13] Qu, C.; Wang, G.; Wu, J.; Yu, X., Neighbor sum distinguishing total choosability of planar graphs, J Comb Optim, 32, 906-916 (2016) · Zbl 1348.05082
[14] Qu, C.; Wang, G.; Wu, J.; Yu, X., On the neighbor sum distinguishing total coloring of planar graphs, Theor Comput Sci, 609, 162-170 (2016) · Zbl 1331.05084
[15] Song, W.; Miao, L.; Duan, Y., Neighbor sum distinguishing total choosability of IC-planar graphs, Discuss Math Graph Theory (2018) · Zbl 1430.05023
[16] 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
[17] Song, H.; Pan, W.; Gong, X.; Xu, C., A note on the neighbor sum distinguishing total coloring of planar graphs, Theor Comput Sci, 640, 125-129 (2016) · Zbl 1345.05035
[18] 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
[19] 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
[20] 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
[21] 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
[22] 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
[23] Zhang, X.; Hou, J.; Liu, G., On total colorings of 1-planar graphs, J Comb Optim, 30, 1, 160-173 (2015) · Zbl 1317.05066
[24] Zhang, X.; Wu, J.; Liu, G., List edge and list total coloring of 1-planar graphs, Front Math China, 7, 5, 1005-1018 (2012) · Zbl 1254.05050
[25] Zhang, X.; Wu, J., On edge colorings of 1-planar graphs, Inf Process Lett, 111, 124-128 (2011) · Zbl 1259.05050
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.