Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree. (English) Zbl 1408.05061
Summary: A proper \([h]\)-total coloring \(c\) of a graph \(G\) is a proper total coloring \(c\) of \(G\) using colors of the set \([h]=\{1,2,\dots,h\}\). Let \(w(u)\) denote the sum of the color on a vertex \(u\) and colors on all the edges incident to \(u\). For each edge \(u_v\in E(G)\), if \(w(u)\neq w(v)\), then we say the coloring \(c\) distinguishes adjacent vertices by sum and call it a neighbor sum distinguishing \([h]\)-total coloring of \(G\). By \(\mathrm{tndi}_\Sigma(G)\), we denote the smallest value \(h\) in such a coloring of \(G\). In this paper, we obtain that \(G\) is a graph with at least two vertices, if \(\mathrm{mad}(G)<3\), then \(\mathrm{tndi}_\Sigma(G)\leq k+2\) where \(k=\max\{\Delta(G),5\}\). It partially confirms the conjecture proposed by M. Pilśniak and M. Woźniak [“On the adjacent vertex distinguishing index by sums in total proper colorings”, Preprint MD 051, Instytut Informatyki i Matematyki Komputerowej, Uniwersytetu Jagiellońskiego].
References:
| [1] | Anholcer, M., Kalkowski, M., Przybyło, J.: A new upper bound for the total vertex irregularity strength of graphs. Discrete Math., 309, 6316–6317 (2009) · Zbl 1210.05117 · doi:10.1016/j.disc.2009.05.023 |
| [2] | Bača, M., Jendrol’, S., Miller, M., et al.: On irregular total labellings. Discrete Math., 307, 1378–1388 (2007) · Zbl 1115.05079 · doi:10.1016/j.disc.2005.11.075 |
| [3] | Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications, North-Holland, New York, 1976 · Zbl 1226.05083 |
| [4] | 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 |
| [5] | Dong, A. J., Wang, G. H.: Neighbor sum distinguishing colorings of some graphs. Discrete Mathematics, Algorithms and Applications, 4(4), 1250047 (2012) · Zbl 1257.05040 · doi:10.1142/S1793830912500474 |
| [6] | Flandrin, E., Saclé, J. F., Marczyk, A., et al.: Neighbor sum distinguishing index. Graphs Combin., 29, 1329–1336 (2013) · Zbl 1272.05047 · doi:10.1007/s00373-012-1191-x |
| [7] | Huang, D. J., Wang, W. F.: Adjacent vertex distinguishing total coloring of planar graphs with large maximum degree (in Chinese). Sci. Sin. Math., 42(2), 151–164 (2012) · doi:10.1360/012011-359 |
| [8] | Li, H. L., Ding L. H., Liu, B. Q., et al.: Neighor sum distinguishing total colorings of planar graphs. J. Combin. Optim., DOI: 10.1007/s10878-013-9660-6 |
| [9] | Li, H. L., Liu, B. Q., Wang, G. H.: Neighor sum distinguishing total colorings of K4-minor free graphs. Front. Math. China, 8(6), 1351–1366 (2013) · Zbl 1306.05066 · doi:10.1007/s11464-013-0322-x |
| [10] | Nurdin, Baskoro, E. T., Salman, A. N. M., Gaos, N. N.: On the total vertex irregularity strength of trees. Discrete Math., 310, 3043–3048 (2010) · Zbl 1208.05014 · doi:10.1016/j.disc.2010.06.041 |
| [11] | Pilśniak, M., Woźniak, M.: On the adjacent vertex distinguishing index by sums in total proper colorings. Preprint MD 051, http://www.ii.uj.edu.pl/preMD/index.php · Zbl 1312.05054 |
| [12] | Przybyło, J.: Linear bound on the irregularity strength and the total vertex irregularity strength of graphs. SIAM J. Discrete Math., 23(1), 511–516 (2009) · Zbl 1216.05135 · doi:10.1137/070707385 |
| [13] | Wang, H. Y.: On the adjacent vertex-distinguishing total chromatic numbers of the graphs with {\(\Delta\)}(G) = 3. J. Comb. Optim., 14, 87–109 (2007) · Zbl 1125.05043 · doi:10.1007/s10878-006-9038-0 |
| [14] | Wang, H. Y.: The adjacent vertex-distinguishing total chromatic number of 1-tree. Ars Combin., 91, 183–192 (2009) · Zbl 1224.05191 |
| [15] | Wang, W. F., Wang, P.: Adjacent vertex distinguishing total coloring of K 4-minor free graphs (in Chinese). Sci. Sin. Math., 39(12), 1462–1472 (2009) |
| [16] | Wang, W. F., Wang, Y. Q.: Adjacent vertex distinguishing total coloring of graphs with lower average degree. Tanwanese J. Math., 12(4), 979–990 (2008) · Zbl 1168.05023 |
| [17] | Wang, Y. Q., Wang, W. F.: Adjacent vertex distinguishing total colorings of outerplanar graphs. J. Comb. Optim., 19, 123–133 (2010) · Zbl 1216.05039 · doi:10.1007/s10878-008-9165-x |
| [18] | Wijaya, K., Surahmat, S., Jendrol’, S.: Total vertex irregular labeling of complete bipartite graphs. J. Combin. Math. Combin. Comput., 55, 129–136 (2005) · Zbl 1100.05090 |
| [19] | Zhang, Z. F., Chen, X. E., Li, J. W., et al.: On adjacent vertex distinguishing total coloring of graphs. Sci. China, Ser. A, 48(3), 289–299 (2005) · Zbl 1080.05036 · 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.
