×

zbMATH — the first resource for mathematics

Neighbor sum distinguishing total coloring of IC-planar graphs with short cycle restrictions. (English) Zbl 1439.05095
Summary: A graph is IC-planar if it admits a drawing in 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)\to\{1,2,\dots,k\}\) is neighbor sum distinguishing if \(f_\phi(u)\neq f_\phi(v)\) for each \(uv\in E(G)\), where \(f_\phi(v)=\sum_{uv\in E(G)}\phi (uv)+\phi(v)\), \(v\in V(G)\). The smallest integer \(k\) in such a coloring of \(G\) is the neighbor sum distinguishing total chromatic number, denoted by \(\chi_\Sigma^{\prime\prime}(G)\). In this paper, by using the discharging method, we prove that \(\chi_\Sigma^{\prime\prime}(G)\leq\max\{\Delta(G)+3,10\}\) if \(G\) is a triangle free IC-planar graph and \(\chi_\Sigma^{\prime\prime}(G)\leq\max\{\Delta(G)+3,13\}\) if \(G\) is an IC-planar graph without adjacent triangles, where \(\Delta(G)\) is the maximum degree of \(G\).
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] Alon, N., Combinatorial nullstellensatz, Combin. Probab. Comput., 8, 7-29 (1999) · Zbl 0920.05026
[2] Bondy, J.; Murty, U., Graph Theory with Applications (1976), North-Holland: North-Holland NewYork · Zbl 1226.05083
[3] 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
[4] Ding, L.; Wang, G.; Wu, J.; Yu, J., Neighbor sum (set) distinguising total choosability via the combinatorial nullstellensatz, Graphs Combin., 33, 4, 885-900 (2017) · Zbl 1371.05078
[5] 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
[6] Ge, S.; Li, J.; Xu, C., Neighbor sum distinguishing total coloring of planar graphs without 5-cycles, Theoret. Comput. Sci., 689, 169-175 (2017) · Zbl 1372.05072
[7] 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
[8] 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
[9] Ma, Q.; Wang, J.; Zhao, H., Neighbor sum distinguishing total colorings of planar graphs without short cycles, Util. Math., 98, 349-359 (2015) · Zbl 1342.05045
[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, W.; Miao, L., Neighbor sum distinguishing total choosability of IC-planar graphs, Discuss. Math. Graph Theory, 40, 331-344 (2020) · Zbl 1430.05023
[13] 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
[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] Song, H.; Xu, C., Neighbor sum distinguishing total coloring of planar graphs without 4-cycles, J. Combin. Optim., 34, 4, 1147-1158 (2017) · Zbl 1378.05073
[16] 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
[17] Wang, J.; Cai, J.; Qiu, B., Neighbor sum distinguishing total choosability of planar graphs without adjacent triangles, Theoret. Comput. Sci., 661, 24, 1-7 (2017) · Zbl 1357.05027
[18] Wang, J.; Ma, Q.; Han, X., Neighbor sum distinguishing total colorings of triangle free planar graphs, Acta Math. Sin. (Engl. Ser.), 31, 2, 216-224 (2015) · Zbl 1317.05065
[19] 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
[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] Zhang, X.; Hou, J.; Liu, G., On total colorings of 1-planar graphs, J. Comb. Optim., 30, 1, 160-173 (2015) · Zbl 1317.05066
[23] 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
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.