Neighbor full sum distinguishing total coloring of graphs

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

Received date: 2020-09-17

  Online published: 2023-03-16

Abstract

Let $f: V(G)\cup E(G)\rightarrow \{1, 2, \cdots, k\}$ be a proper $k$-total coloring of $G$. Set $\phi(x)=f(x)+\sum\limits_{e\ni x}f(e)+\sum\limits_{y\in N(x)}f(y)$, where $N(x)=\{y\in V(G)|xy\in E(G)\}$. If $\phi(u)\neq \phi(v)$ for any edge $uv\in E(G)$, then $f$ is called a $k$-neighbor full sum distinguishing total coloring of $G$. The smallest value $k$ for which $G$ has such a coloring is called the neighbor full sum distinguishing total chromatic number of $G$ and denoted by $ftndi_{\sum}(G)$. In this paper, we obtain this parameter for paths, cycles, stars, wheels, complete bipartite graphs, complete graphs and trees. Meanwhile, we conjecture that the neighbor full sum distinguishing total chromatic number of $G(\neq K_2)$ is not more than $\Delta(G)+2$.

Cite this article

Fuxiang CUI, Chao YANG, Hongbo YE, Bing YAO . Neighbor full sum distinguishing total coloring of graphs[J]. Operations Research Transactions, 2023 , 27(1) : 149 -158 . DOI: 10.15960/j.cnki.issn.1007-6093.2023.01.011

References

1 Bondy J A , Murty U S R . Graph Theory with Applications[M]. London: The MaCmillan Press ltd, 1976.
2 Vizing V G . On an estimate of the chromatic class of a $ p$-graph[J]. Diskret Analiz, 1964, 3 (1): 25- 30.
3 Behzad M. Graphs and their chromatic numbers[D]. East Lansing: Michigan State University, 1965.
4 Zhang Z F , Chen X E , Li J W , et al. On the adjacent vertex-distinguishing total coloring of graphs[J]. Science in China Series A Mathematics, 2005, 48 (3): 289- 299.
5 Karonski M , Luczak T , Thomason A . Edge weights and vertex colours[J]. Journal of Combinatorial Theory: Series B, 2004, 91, 151- 157.
6 Pilsniak M , Wozniak M . On a 1,2 conjecture[J]. Discrete Mathematics and Theoretical Computer Science, 2010, 12 (1): 101- 108.
7 Dong A J , Wang G H . Neighbor sum distinguishing total colorings of graphs with bounded maximum average degree[J]. Acta Mathematica Sinica (English Series), 2014, 30 (4): 703- 709.
8 Pilsniak M , Wozniak M . On the total-neighbor-distinguishing index by sums[J]. Graphs and Combinatorics, 2015, 31 (3): 771- 782.
9 Flandrin E , Li H , Marczyk A , et al. A note on neighbor expanded sum distinguishing index[J]. Discussiones Mathematicae Graph Theory, 2017, 37 (1): 29- 37.
10 潘玉美, 莫明忠. 完全二部图全着色的构造[J]. 广西科学院学报, 2010, 26 (1): 7- 8.7-8, 12
11 田永成, 田新, 田永兴, 等. $ n$阶完全图全着色的构造及其推广[J]. 东北大学学报(自然科学版), 2002, 23 (1): 1- 4.
Outlines

/