×

zbMATH — the first resource for mathematics

Neighbor sum distinguishing total chromatic number of planar graphs without 5-cycles. (English) Zbl 1430.05044
Summary: For a given graph \(G = (V (G), E(G))\), a proper total coloring \(\varphi : V (G) \cup E(G) \rightarrow \{1, 2, \dots, k\}\) is neighbor sum distinguishing if \(f(u) \neq f(v)\) for each edge \(uv \in E(G)\), where \(f(v) = \Sigma_{ uv \in E(G)} \varphi (uv)+ \varphi (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^{\prime\prime}_\Sigma( G )\). M. Pilśniak and M. Woźniak [Graphs Comb. 31, No. 3, 771–782 (2015; Zbl 1312.05054)] first introduced this coloring and conjectured that \(\chi^{\prime\prime}_\Sigma(G)\le \Delta ( G ) + 3\) for any graph with maximum degree \(\Delta (G)\). In this paper, by using the discharging method, we prove that for any planar graph \(G\) without 5-cycles, \(\chi^{\prime\prime}_\Sigma ( G ) \le \max \left\{ \Delta ( G ) + 2,10\right\}\). The bound \(\Delta (G) + 2\) is sharp. Furthermore, we get the exact value of \(\chi^{\prime\prime}_\Sigma( G )\) if \(\Delta (G) \geq 9\).
MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, NewYork-Amsterdam-Oxford, 1982). · Zbl 1226.05083
[2] X. Cheng, D. Huang, G. Wang and J. Wu, Neighbor sum distinguishing total colorings of planar graphs with maximum degree Δ, Discrete Appl. Math. 190-191 (2015) 34-41. doi:10.1016/j.dam.2015.03.013
[3] A. Dong and G. Wang, Neighbor sum distinguising total colorings of graphs with bounded maximum average degree, Acta Math. Sin. (Engl. Ser.) 30 (2014) 703-709. doi:10.1007/s10114-014-2454-7 · Zbl 1408.05061
[4] L. Ding, G. Wang and G. Yan, Neighbor sum distinguising total colorings via the Combinatorial Nullstellensatz, Sci. China Math. 57 (2014) 1875-1882. doi:10.1007/s11425-014-4796-0
[5] S. Ge, J. Li and C. Xu, Neighbor sum distinguishing total chromatic number of planar graphs without 4-cycles, Util. Math. 105 (2017) 259-265. · Zbl 1398.05087
[6] S. Ge, J. Li and C. Xu, Neighbor sum distinguishing total coloring of planar graphs without 5-cycles, Theoret. Comput. Sci. 689 (2017) 169-175. doi:10.1016/j.tcs.2017.05.037 · Zbl 1372.05072
[7] H. Li, L. Ding, B. Liu and G. Wang, Neighbor sum distinguishing total colorings of planar graphs, J. Comb. Optim. 30 (2015) 675-688. doi:10.1007/s10878-013-9660-6 · Zbl 1325.05083
[8] J. Li, S. Ge and C. Xu, Neighbor sum distinguishing total colorings of planar graphs with girth at least 5, Util. Math. 104 (2017) 115-121. · Zbl 1383.05108
[9] H. Li, B. Liu and G. Wang, Neighbor sum distinguishing total colorings of K_4-minor free graphs, Front. Math. China 8 (2013) 1351-1366. doi:10.1007/s11464-013-0322-x · Zbl 1306.05066
[10] Q. Ma, J. Wang and H. Zhao, Neighbor sum distinguishing total colorings of planar graphs without short cycles, Util. Math. 98 (2015) 349-359. · Zbl 1342.05045
[11] M. Pilśniak and M. Woźniak, On the total-neighbor-distinguishing index by sums, Graphs Combin. 31 (2015) 771-782. doi:10.1007/s00373-013-1399-4
[12] C. Qu, G. Wang, J. Wu and X. Yu, On the neighbor sum distinguishing total coloring of planar graphs, Theoret. Comput. Sci. 609 (2016) 162-170. doi:10.1016/j.tcs.2015.09.017 · Zbl 1331.05084
[13] C. Qu, G. Wang, G. Yan and X. Yu, Neighbor sum distinguishing total choosability of planar graphs, J. Comb. Optim. 32 (2016) 906-916. doi:10.1007/s10878-015-9911-9 · Zbl 1348.05082
[14] H. Song, W. Pan, X. Gong and C. Xu, A note on the neighbor sum distinguishing total coloring of planar graphs, Theoret. Comput. Sci. 640 (2016) 125-129. doi:10.1016/j.tcs.2016.06.007 · Zbl 1345.05035
[15] H. Song and C. Xu, Neighbor sum distinguishing total chromatic number of K_4-minor free graph, Front. Math. China 12 (2017) 937-947. doi:10.1007/s11464-017-0649-9 · Zbl 1371.05097
[16] H. Song and C. Xu, Neighbor sum distinguishing total coloring of planar graphs without 4-cycles, J. Comb. Optim. 34 (2017) 1147-1158. doi:10.1007/s10878-017-0137-x · Zbl 1378.05073
[17] J. Wang, J. Cai and Q. Ma, Neighbor sum distinguishing total choosability of planar graphs without 4-cycles, Discrete Appl. Math. 206 (2016) 215-219. doi:10.1016/j.dam.2016.02.003 · Zbl 1335.05051
[18] J. Wang, J. Cai and B. Qiu, Neighbor sum distinguishing total choosability of planar graphs without adjacent triangles, Theoret. Comput. Sci. 661 (2017) 1-7. doi:10.1016/j.tcs.2016.11.003 · Zbl 1357.05027
[19] J. Wang, Q. Ma and X. Han, Neighbor sum distinguishing total colorings of triangle free planar graphs, Acta Math. Sin. (Engl. Ser.) 31 (2015) 216-224. doi:10.1007/s10114-015-4114-y · Zbl 1317.05065
[20] D. Yang, X. Yu, L. Sun, J. Wu and S. Zhou, Neighbor sum distinguishing total chromatic number of planar graphs with maximum degree 10, Appl. Math. Comput. 314 (2017) 456-468. doi:10.1016/j.amc.2017.06.002 · Zbl 1426.05051
[21] J. Yao, X. Yu, G. Wang and C. Xu, Neighbor sum distinguishing total coloring of 2-degenerate graphs, J. Comb. Optim. 34 (2017) 64-70. doi:10.1007/s10878-016-0053-5 · Zbl 1394.05037
[22] J. Yao, X. Yu, G. Wang and C. Xu, Neighbor sum (set) distinguishing total choosability of d-degenerate graphs, Graphs Combin. 32 (2016) 1611-1620. doi:10.1007/s00373-015-1646-y · 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.