d-维网格的星边染色

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

d-维网格的星边染色

邓凯¹, 刘信生², 田双亮¹

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 ¹, LIU Xin-sheng ², TIAN Shuang-liang¹

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

摘要： 研究图~ $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

中图分类号:

O157.5

邓凯, 刘信生, 田双亮. d-维网格的星边染色[J]. 华东师范大学学报(自然科学版), 2012, 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 Sc, 2012, 2012(3): 13-16.

参考文献

{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.

编辑推荐 0

Metrics

阅读次数

全文

2685

HTML			PDF

最新录用	在线预览	正式出版	最新录用	在线预览	正式出版
0	0	0	0	0	2685

来源	本网站	其他网站

次数	188	2497
比例	7%	93%

摘要

2449

最新录用	在线预览	正式出版

0	0	2449

来源	本网站	其他网站

次数	251	2198
比例	10%	90%

[1]	刘信生, 路伟华. 图的点可区别星边色数的一个上界[J]. 华东师范大学学报(自然科学版), 2012, 2012(5): 120-126.
[2]	陈明;陈宝兴. 折叠超立方体的谱[J]. 华东师范大学学报(自然科学版), 2011, 2011(2): 39-46，6.