Star edge coloring of $d$-dimensional grids

DENG Kai; LIU Xin-sheng; TIAN Shuang-liang

Issue 3

May 2012

Turn off MathJax

Article Contents

Article Navigation > Journal of East China Normal University (Natural Sciences) > 2012 > (3): 13-16

DENG Kai, LIU Xin-sheng, TIAN Shuang-liang. Star edge coloring of $d$-dimensional grids[J]. Journal of East China Normal University (Natural Sciences), 2012, (3): 13-16.

Citation:

DENG Kai, LIU Xin-sheng, TIAN Shuang-liang. Star edge coloring of $d$-dimensional grids[J]. Journal of East China Normal University (Natural Sciences), 2012, (3): 13-16.

DENG Kai, LIU Xin-sheng, TIAN Shuang-liang. Star edge coloring of $d$-dimensional grids[J]. Journal of East China Normal University (Natural Sciences), 2012, (3): 13-16.

Citation:

DENG Kai, LIU Xin-sheng, TIAN Shuang-liang. Star edge coloring of $d$-dimensional grids[J]. Journal of East China Normal University (Natural Sciences), 2012, (3): 13-16.

PDF( 243 KB)

Star edge coloring of $d$-dimensional grids

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 Date: 2011-04-01
Rev Recd Date: 2011-07-01
Publish Date: 2012-05-25

Abstract

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.
- star edge coloring,
- star chromatic index,
- hypercube,
- $d$-dimensional grid

FullText(HTML)

References(1)

References

[1]

{1}GR\"{U}NBAUM B. Acyclic colourings of planar graphs[J]. Isreal J Math, 1973, 14(3): 390-408.
{2}FERTIN G, RASPAUD A, REED B. Star coloring of graphs[J]. J Graph Theory, 2004, 47(3): 163-182.
{3}刘信生, 邓凯. 最大度不小于7的图的星边色数的一个上界[J]. 兰州大学学报: 自然科学版, 2008, 44(2): 98-100.
{4}邓凯. 图的星边染色[D]. 兰州: 西北师范大学, 2007.
{5}杨玉红, 刘信生, 陈祥恩. 联图~$P_{m}\vee P_{n}$\,的星边染色[J]. 西北师范大学学报: 自然科学版, 2008, 44(6): 26-28.
{6}邓凯. 最大度为3的2-连通外平面图的星边染色[J]. 东北师范大学学报: 自然科学版, 2011, 43(2): 7-10.
{7}邓凯, 刘信生, 田双亮. 树的星边染色[J]. 山东大学学报: 理学版, 2011,46(8): 84-88.
{8}BONDY J A, MURTY U S R. Graph Theory with Applications[M]. London: Macmillan Press, 1976.
{9}陈明, 陈宝兴. 折叠超立方体的谱[J]. 华东师范大学学报: 自然科学版, 2011(2): 39-46.

Relative Articles

Supplements(0)

Cited By

Proportional views