Star edge coloring of $d$-dimensional grids
-
摘要: 研究图~$G$\,的星边色数~$\chi_{s}^{\prime}(G)$\,与其顶点数~$\nu$ 和边数~$\varepsilon$\,之间的关系. 证明了当~$\Delta(G)\geqslant2$\,时, 有~$\lceil\frac{8\varepsilon}{3\nu}\rceil\leqslant\chi_{s}^{\prime}(G)$. 得到了~$2$-维网格的星边色数, 并且给出了超立方体和~$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
-
[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. -
点击查看大图
计量
- 文章访问数: 2364
- HTML全文浏览量: 24
- PDF下载量: 2414
- 被引次数: 0
下载: