华东师范大学学报(自然科学版) ›› 2012, Vol. 2012 ›› Issue (5): 120-126.

• 应用数学 • 上一篇    下一篇

图的点可区别星边色数的一个上界

刘信生, 路伟华   

  1. 西北师范大学, 数学与信息科学学院, 兰州 730070
  • 收稿日期:2011-10-01 修回日期:2012-02-01 出版日期:2012-09-25 发布日期:2012-09-29

An upper bound for the vertex-distinguishing star edge chromatic number of graphs

LIU Xin-sheng, LU Wei-hua   

  1. College of Mathematics and Information Science, Northwest Normal University, Lanzhou 730070, China
  • Received:2011-10-01 Revised:2012-02-01 Online:2012-09-25 Published:2012-09-29

PDF

2621

摘要： 图\,$G$\,的点可区别星边边色数, 记为\,$\chi'_{\rm vds}{(G)}$, 是图\,$G$\,的点可区别星边染色所用色的最小数目. 得到了一些特殊图的星边染色,
并证明了若图\,$G$\,是一个最小度不小于\,5, 且顶点数不超过\,$\Delta^7$\,的图时, $\chi'_{\rm vds}{(G)}\leqslant {14\Delta^{2}}$, 其中\,$\Delta$\,是图\,$G$\,的最大度.

关键词: 点可区别边色数, 点可区别星边色数, 概率方法

Abstract: The vertex-distinguishing star edge chromatic number of $G$, denoted by $\chi'_{\rm vds}{(G)}$, is the minimum number of colors in a vertex-distinguishing star edge coloring of $G$. The vertex-distinguishing star edge colorings of some particular graphs were obtained. Furthermore, if $G(V,E)$ is a graph with $\delta\geqslant 5$, and $n\leqslant  \Delta^7$, then $\chi'_{\rm vds}{(G)}\leqslant 14\Delta^2$, where $n$ is the order of $G$,
$\delta(G)$ is the minimum degree of $G$, and $\Delta(G)$ is the maximum\linebreak degree of $G$.

Key words: vertex-distinguishing edge chromatic number, vertex-distinguishing star edge chromatic number, probability method

中图分类号: