# zbMATH — the first resource for mathematics

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].

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C07 Vertex degrees
##### Keywords:
total coloring; neighbor sum; average degree
Full Text:
##### References:
  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  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  Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications, North-Holland, New York, 1976 · Zbl 1226.05083  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  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  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  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  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  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  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  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  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  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  Wang, H. Y.: The adjacent vertex-distinguishing total chromatic number of 1-tree. Ars Combin., 91, 183–192 (2009) · Zbl 1224.05191  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)  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  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  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  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. 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.