华东师范大学学报(自然科学版) ›› 2013, Vol. 2013 ›› Issue (6): 57-67.

• 应用数学与基础数学 • 上一篇    下一篇

广义~Petersen~图在四种可区分条件下的全染色

杨 超, 姚 兵, 王宏宇   

  1. 西北师范大学 数学与统计学院, 兰州 730070
  • 收稿日期:2012-11-01 修回日期:2013-03-01 出版日期:2013-11-25 发布日期:2014-01-13

Generalized Petersen graphs admit proper total colorings with four distinguishing constraints

YANG Chao, YAO Bing, WANG Hong-yu   

  1. College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China
  • Received:2012-11-01 Revised:2013-03-01 Online:2013-11-25 Published:2014-01-13

PDF

2146

摘要： 关于图的可区别染色的研究起源于移动通信的频率分配问题.
本文定义了简单图G的一个4-邻点可区别全染色. 对一个图G进行
4-邻点可区别全染色所需的最少颜色数称为图G的
4-邻点可区别全色数, 记为~$\chi^{\prime\prime}_{4as}(G)$.
对于广义~Petersen~图~$P(n,k)$, $6\leq \chi^{\prime\prime}_{4as}
(P(n,k))\leq 7$ 得到证明.

关键词: 全染色, 点可区别全染色, 广义~Petersen~图

Abstract: The study of distinguishing coloring in graphs is derived
from the frequency assignment problem in mobile communications. This
paper introduced the concept of $4$-adjacent vertex distinguishing
total coloring ($4$-avdtc) of a simple graph $G$. The minimum number
of $k$ colors required for $G$ such that it satisfies a $4$-avdtc is
denoted as $\chi^{\prime\prime}_{4as}(G)$. For generalized Petersen
graphs $P(n,k)$, it was proved that $6\leq
\chi^{\prime\prime}_{4as}(P(n,k))\leq 7$.

Key words: total coloring, vertex distinguishing total colorings, generalized Petersen graphs

中图分类号: