Neighbor sum distinguishing total colorings of corona of subcubic graphs. (English) Zbl 1470.05053
Summary: A proper \([k]\)-total coloring \(c\) of a graph \(G\) is a proper total coloring \(c\) of \(G\) using colors of the set \([k]=\{1,2,\ldots ,k\}\). Let \(\Sigma (u)\) denote the sum of the color on a vertex \(u\) and the colors on all the edges incident with \(u\). For each edge \(uv \in E(G)\), if \(\Sigma (u) \neq \Sigma (v)\), then we say the coloring distinguishes adjacent vertices by sum and call it a neighbor sum distinguishing total coloring of \(G\). By \(tndi_{\Sigma }(G)\), we denote the minimal value of \(k\) in such a coloring of \(G\). It has been conjectured by M. Pilśniak and M. Woźniak [Graphs Comb. 31, No. 3, 771–782 (2015; Zbl 1312.05054)] that \(\Delta (G)+3\) colors enable the existence of a neighbor sum distinguishing total coloring. In this paper, we consider the neighbor sum distinguishing total coloring of corona product \(G \circ H\) and obtain that \(tndi_{\Sigma }(G \circ H) \leq \Delta (G \circ H)+3\).
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
Citations:
Zbl 1312.05054References:
| [1] | Bondy, JA; Murty, USR, Graph Theory with Applications (1976), New York: North-Holland, New York · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2 |
| [2] | Chen, X., On the adjacent vertex distinguishing total coloring numbers of graphs with \(\Delta =3\), Discrete Math., 308, 4003-4008 (2008) · Zbl 1203.05052 · doi:10.1016/j.disc.2007.07.091 |
| [3] | Cheng, XH; Wang, GH; Wu, JL, The adjacent vertex distinguishing total chromatic numbers of planar graphs \(\Delta =10\), J. Combin. Optim., 34, 2, 383-397 (2017) · Zbl 1376.05052 · doi:10.1007/s10878-016-9995-x |
| [4] | Ding, LH; Wang, GH; Yan, GY, Neighbor sum distinguishing total colorings via the combinatorial Nullstellensatz, Sci. China Ser. A: Math., 57, 9, 1875-1882 (2014) · Zbl 1303.05058 · doi:10.1007/s11425-014-4796-0 |
| [5] | Ding, LH; Wang, GH; Wu, JL; Yu, JG, Neighbor sum (set) distinguishing total choosability via the combinatorial Nullstellensatz, Graphs Combin., 33, 4, 885-900 (2017) · Zbl 1371.05078 · doi:10.1007/s00373-017-1806-3 |
| [6] | Dong, AJ; Wang, GH, Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree, Acta Math. Sin., 30, 4, 703-709 (2014) · Zbl 1408.05061 · doi:10.1007/s10114-014-2454-7 |
| [7] | Frucht, R.; Harary, F., On the corona of two graphs, Aequ. Math., 4, 322-325 (1970) · Zbl 0198.29302 · doi:10.1007/BF01844162 |
| [8] | Ge, S.; Li, JG; Xu, CQ, Neighbor sum distinguishing total coloring of planar graphs without \(5\)-cycles, Theor. Comput. Sci., 689, 169-175 (2017) · Zbl 1372.05072 · doi:10.1016/j.tcs.2017.05.037 |
| [9] | Huang, DJ; Wang, WF, Adjacent vertex distinguishing total coloring of planar graphs with large maximum degree, Sci. Sin. Math., 42, 2, 151-164 (2012) · Zbl 1488.05182 · doi:10.1360/012011-359 |
| [10] | Johnson, MA, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Stat., 3, 203-236 (1993) · Zbl 0800.92106 · doi:10.1080/10543409308835060 |
| [11] | Khuller, S.; Raghavachari, B.; Rosenfeld, A., Landmarks in graphs, Discrete Appl. Math., 70, 3, 217-229 (1996) · Zbl 0865.68090 · doi:10.1016/0166-218X(95)00106-2 |
| [12] | Laïche, D.; Bouchemakh, I., Paching coloring of some undirected and oriented corona graphs, Discuss. Math. Graph Theory, 37, 665-690 (2017) · Zbl 1366.05044 · doi:10.7151/dmgt.1963 |
| [13] | Li, HL; Liu, BQ; Wang, GH, Neighbor sum distinguishing total colorings of \(K_4\)-minor free graphs, Front. Math. China, 8, 6, 1351-1366 (2013) · Zbl 1306.05066 · doi:10.1007/s11464-013-0322-x |
| [14] | Li, HL; Ding, LH; Liu, BQ; Wang, GH, Neighbor sum distinguishing total colorings of planar graphs, J. Combin. Optim., 30, 3, 675-688 (2015) · Zbl 1325.05083 · doi:10.1007/s10878-013-9660-6 |
| [15] | Li, JA; Luo, R.; Miao, ZK, Adjacent vertex distinguishing total coloring of graphs with maximum degree \(4\), Discrete Math., 340, 2, 119-123 (2017) · Zbl 1351.05084 · doi:10.1016/j.disc.2016.07.011 |
| [16] | Lu, Y.; Xu, CD; Miao, ZK, Neighbor sum distinguishing list total coloring of subcubic graphs, J. Combin. Optim., 35, 3, 778-793 (2018) · Zbl 1387.05094 · doi:10.1007/s10878-017-0239-5 |
| [17] | Miao, ZK; Shi, R.; Hu, XL; Luo, R., Adjacent vertex distinguishing total colorings of \(2\)-degenerate graph, Discrete Math., 336, 2446-2449 (2016) · Zbl 1339.05141 · doi:10.1016/j.disc.2016.03.019 |
| [18] | Mohan, S.; Geetha, J.; Somasundaram, K., Total coloring of the corona product of two graphs, Australas. J. Combin., 68, 1, 15-22 (2017) · Zbl 1375.05101 |
| [19] | Pilśniak, M.; Woźniak, M., On the total-neighbor-distinguishing index by sums, Graphs Combin., 31, 3, 771-782 (2015) · Zbl 1312.05054 · doi:10.1007/s00373-013-1399-4 |
| [20] | Qu, CQ; Wang, GH; Wu, JL; Yu, XW, On the neighbor sum distinguishing total coloring of planar graphs, Theor. Comput. Sci., 609, 162-170 (2016) · Zbl 1331.05084 · doi:10.1016/j.tcs.2015.09.017 |
| [21] | Song, WY; Miao, LY; Li, JB; Zhao, YY; Pang, JR, Neighbor sum distinguishing total coloring of sparse IC-planar graphs, Discrete Appl. Math., 239, 183-192 (2018) · Zbl 1382.05019 · doi:10.1016/j.dam.2017.11.028 |
| [22] | Thirusangu, K.; Ezhilarasi, R., Adjacent vertex distinguishing total coloring of line and splitting graph of some graphs, Ann. Pure Appl. Math., 13, 2, 173-183 (2017) · doi:10.22457/apam.v13n2a3 |
| [23] | Vizing, VG, On an estimate of the chromatic class of a \(P\)-graph, Metody Diskret. Analiz., 3, 25-30 (1964) · Zbl 1539.05042 |
| [24] | Wang, HY, On the adjacent vertex-distinguishing total chromatic numbers of the graphs with \(\Delta (G)=3\), J. Combin. Optim., 14, 87-109 (2007) · Zbl 1125.05043 · doi:10.1007/s10878-006-9038-0 |
| [25] | Wang, HY, The adjacent vertex-distinguishing total chromatic number of \(1\)-tree, ARS Combin., 91, 183-192 (2009) · Zbl 1224.05191 |
| [26] | Wang, WF; Wang, YQ, Adjacent vertex distinguishing total coloring of graphs with lower average degree, Tanwanese J. Math., 12, 4, 979-990 (2008) · Zbl 1168.05023 |
| [27] | Wang, WF; Wang, P., Adjacent vertex distinguishing total coloring of \(K_4\)-minor free graphs, Sci. Sin. Math., 39, 12, 1462-1472 (2009) |
| [28] | Wang, YQ; Wang, WF, Adjacent vertex distinguishing total colorings of outerplanar graphs, J. Combin. Optim., 19, 123-133 (2010) · Zbl 1216.05039 · doi:10.1007/s10878-008-9165-x |
| [29] | Wang, WF; Huang, DJ, The adjacent vertex distinguishing total coloring of planar graphs, J. Combin. Optim., 27, 2, 379-396 (2014) · Zbl 1319.90076 · doi:10.1007/s10878-012-9527-2 |
| [30] | Xu, CQ; Li, JG; Ge, S., Neighbor sum distinguishing total chromatic number of planar graphs, Appl. Math. Comput., 332, 189-196 (2018) · Zbl 1427.05093 |
| [31] | Yang, DL; Sun, L.; Yu, XW; Wu, JL; 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 |
| [32] | Yao, JJ; Yu, XW; Wang, GH; Xu, CQ, Neighbor sum distinguishing total coloring of \(2\)-degenerate graphs, J. Combin. Optim., 34, 1, 64-70 (2017) · Zbl 1394.05037 · doi:10.1007/s10878-016-0053-5 |
| [33] | Zhang, ZF; Chen, XE; Li, JW; Yao, B.; Lu, XZ; Wang, JF, On adjacent vertex distinguishing total coloring of graphs, Sci. China Ser. A Math., 48, 3, 289-299 (2005) · Zbl 0854.76074 · doi:10.1360/03YS0207 |
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.
