Let $ f $ be a proper total $ k $-coloring of a simple graph $ G $ from $ V(G)\cup E(G) $ to $ \{1, 2, \dots, k\} $, let $ C(u, f) $ be the set of the colors assigned to the edges incident with $ u $, and let $ n_d(G) $ and $ \Delta(G) $ denote the number of all vertices of degree $ d $ and the maximum degree in $ G $, respectively. We call $ f $ a (2)-vertex distinguishing total $ k $-coloring ($ k $-(2)-vdc for short) if $ C(u, f)\neq C(v, f) $ and $ C(u, f)\cup \{f(u)\}\neq C(v, f)\cup \{f(v)\} $ for distinct vertices $ u, v\in V(G) $. The minimum number $ k $ of colors required for which $ G $ admits a $ k $-(2)-vdc is denoted by $ \chi''_{2s}(G) $. In this paper, we show that a tree $ T $ with $ n_2(T)\leq n_1(T) $ has $ \chi''_{2s}(T) = n_1(T) $ if and only if $ T $ is not a tree with $ D(T) = 2, 3 $ or $ n_1(T) = \Delta(T) $, where $ D(T) $ is the diameter of tree $ T $.
Citation: Chao Yang, Bing Yao, Zhi-xiang Yin. A new vertex distinguishing total coloring of trees[J]. AIMS Mathematics, 2021, 6(9): 9468-9475. doi: 10.3934/math.2021550
Let $ f $ be a proper total $ k $-coloring of a simple graph $ G $ from $ V(G)\cup E(G) $ to $ \{1, 2, \dots, k\} $, let $ C(u, f) $ be the set of the colors assigned to the edges incident with $ u $, and let $ n_d(G) $ and $ \Delta(G) $ denote the number of all vertices of degree $ d $ and the maximum degree in $ G $, respectively. We call $ f $ a (2)-vertex distinguishing total $ k $-coloring ($ k $-(2)-vdc for short) if $ C(u, f)\neq C(v, f) $ and $ C(u, f)\cup \{f(u)\}\neq C(v, f)\cup \{f(v)\} $ for distinct vertices $ u, v\in V(G) $. The minimum number $ k $ of colors required for which $ G $ admits a $ k $-(2)-vdc is denoted by $ \chi''_{2s}(G) $. In this paper, we show that a tree $ T $ with $ n_2(T)\leq n_1(T) $ has $ \chi''_{2s}(T) = n_1(T) $ if and only if $ T $ is not a tree with $ D(T) = 2, 3 $ or $ n_1(T) = \Delta(T) $, where $ D(T) $ is the diameter of tree $ T $.
[1] | P. N. Balister, A. Kostochka, H. Li, R. H. Schelp, Balanced edge colorings, J. Comb. Theory B, 90 (2004), 3–20. doi: 10.1016/S0095-8956(03)00073-X |
[2] | P. N. Balister, B. Bollob$\acute{a}$s, R. H. Schelp, Vertex distinguishing coloring of graphs with $\Delta(G)$ = 2, Discrete Math., 252 (2002), 17–29. doi: 10.1016/S0012-365X(01)00287-4 |
[3] | A. C. Burris, R. H. Schelp, Vertex-distingushing proper edge-colorings, J. Graph Theory, 26 (1997), 73–82. doi: 10.1002/(SICI)1097-0118(199710)26:2<73::AID-JGT2>3.0.CO;2-C |
[4] | J. Černý, M. Horňák, R. Soták, Observability of a graph, Math. Slovaca, 46 (1996), 21–31. |
[5] | B. Yao, Z. F. Zhang, J. F. Wang, Some results on spanning trees, Acta Math. Appl. Sin. Engl. Ser., 26 (2010), 607–616. doi: 10.1007/s10255-010-0011-4 |