华东师范大学学报(自然科学版) ›› 2012, Vol. 2012 ›› Issue (3): 13-16.

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

d-维网格的星边染色

邓 凯1, 刘信生2, 田双亮1   

  1. 1. 西北民族大学~~数学与计算机科学学院, 兰州 730030; 2. 西北师范大学~~数学与信息科学学院, 兰州 730070
  • 收稿日期:2011-04-01 修回日期:2011-07-01 出版日期:2012-05-25 发布日期:2012-05-22

Star edge coloring of $d$-dimensional grids

DENG Kai 1,  LIU Xin-sheng 2, TIAN Shuang-liang1   

  1. 1. College of Mathematics and Computer Science, Northwest University for Nationalities, Lanzhou 730030, China; 2. College of Mathematics and Information Science, Northwest Normal University, Lanzhou 730070, China
  • Received:2011-04-01 Revised:2011-07-01 Online:2012-05-25 Published:2012-05-22

PDF

2655

摘要： 研究图~$G$\,的星边色数~$\chi_{s}^{\prime}(G)$\,与其顶点数~$\nu$ 和边数~$\varepsilon$\,之间的关系. 证明了当~$\Delta(G)\geqslant2$\,时, 有~$\lceil\frac{8\varepsilon}{3\nu}\rceil\leqslant\chi_{s}^{\prime}(G)$. 得到了~$2$-维网格的星边色数, 并且给出了超立方体和~$d$-维网格的星边色数的可达上界和下界.

关键词: 星边染色, 星边色数, 超立方体, $d$-维网格

Abstract: The star chromatic index of graph $G$ is denoted by $\chi_{s}^{\prime}(G)$. In this paper, we studied the relationship between  $\chi_{s}^{\prime}(G)$, $|V(G)|=\nu$, and $|E(G)|=\varepsilon$, and proved that $\lceil\frac{8\varepsilon}{3\nu}\rceil\leqslant\chi_{s}^{\prime}(G)$ for $\Delta(G)\geqslant2$. The star chromatic index of 2-dimensional grid was obtained. We also got the attainable bounds for the star chromatic index of hypercubes and $d$-dimensional grids.

Key words: star edge coloring, star chromatic index, hypercube, $d$-dimensional grid

中图分类号: