A new vertex distinguishing total coloring of trees

Chao Yang; Bing Yao; Zhi-xiang Yin; Chao Yang; Bing Yao; Zhi-xiang Yin

doi:10.3934/math.2021550

AIMS Mathematics

2021, Volume 6, Issue 9: 9468-9475. doi: 10.3934/math.2021550

Previous Article Next Article

Research article

A new vertex distinguishing total coloring of trees

1.
Center of Intelligent Computing and Applied Statistics, School of Mathematics, Physics and Statistics, Shanghai University of Engineering Science, Shanghai 201620, China
2.
College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China

Received: 26 February 2021 Accepted: 16 June 2021 Published: 23 June 2021
MSC : 05C15

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 $.
- vertex distinguishing coloring,
- total coloring,
- trees
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

Related Papers:

Abstract

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

References

[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

Reader Comments

Your name:*

Email:*
© 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)