图的邻点全和可区别全染色

展开
  • 1. 上海工程技术大学数理与统计学院, 上海 201620
    2. 上海工程技术大学智能计算与应用统计研究中心, 上海 201620
    3. 西北师范大学数学与统计学院, 甘肃兰州 730070
杨超, E-mail: yangchaomath0524@163.com

收稿日期: 2020-09-17

  网络出版日期: 2023-03-16

基金资助

国家自然科学基金(61163054);国家自然科学基金(61363060);国家自然科学基金(61662066)

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

摘要

$f:V(G)\cup E(G)\rightarrow \{1, 2, \cdots, k\}$是图$G$的一个正常$k$-全染色。令$\phi(x)=f(x)+\sum\limits_{e\ni x}f(e)+\sum\limits_{y\in N(x)}f(y)$, 其中$N(x)=\{y\in V(G)|xy\in E(G)\}$。对任意的边$uv\in E(G)$, 若有$\phi(u)\neq \phi(v)$成立, 则称$f$是图$G$的一个邻点全和可区别$k$-全染色。图$G$的邻点全和可区别全染色中最小的颜色数$k$叫做$G$的邻点全和可区别全色数, 记为$ftndi_{\sum}(G)$。本文确定了路、圈、星、轮、完全二部图、完全图以及树的邻点全和可区别全色数, 同时猜想: 简单图$G(\neq K_2)$的邻点全和可区别全色数不超过$\Delta(G)+2$

本文引用格式

崔福祥, 杨超, 叶宏波, 姚兵 . 图的邻点全和可区别全染色[J]. 运筹学学报, 2023 , 27(1) : 149 -158 . DOI: 10.15960/j.cnki.issn.1007-6093.2023.01.011

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

参考文献

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.
文章导航

/