Journal of East China Normal University(Natural Sc ›› 2012, Vol. 2012 ›› Issue (3): 13-16.

• Article • Previous Articles     Next Articles

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

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

CLC Number: