图的点可区别星边色数的一个上界

刘信生; 路伟华

图的点可区别星边色数的一个上界

1.
西北师范大学, 数学与信息科学学院, 兰州 730070

详细信息

中图分类号: O157.5
计量
- 文章访问数: 2231
- HTML全文浏览量: 67
- PDF下载量: 2444
- 被引次数: 0
出版历程
- 收稿日期: 2011-10-01
- 修回日期: 2012-02-01
- 刊出日期: 2012-09-25

An upper bound for the vertex-distinguishing star edge chromatic number of graphs

1.
College of Mathematics and Information Science, Northwest Normal University, Lanzhou 730070, China

摘要

摘要: 图\,$G$\,的点可区别星边边色数, 记为\,$\chi'_{\rm vds}{(G)}$, 是图\,$G$\,的点可区别星边染色所用色的最小数目. 得到了一些特殊图的星边染色, 并证明了若图\,$G$\,是一个最小度不小于\,5, 且顶点数不超过\,$\Delta^7$\,的图时, $\chi'_{\rm vds}{(G)}\leqslant {14\Delta^{2}}$, 其中\,$\Delta$\,是图\,$G$\,的最大度.
- 点可区别边色数 /
- 点可区别星边色数 /
- 概率方法
Abstract: The vertex-distinguishing star edge chromatic number of $G$, denoted by $\chi'_{\rm vds}{(G)}$, is the minimum number of colors in a vertex-distinguishing star edge coloring of $G$. The vertex-distinguishing star edge colorings of some particular graphs were obtained. Furthermore, if $G(V,E)$ is a graph with $\delta\geqslant 5$, and $n\leqslant \Delta^7$, then $\chi'_{\rm vds}{(G)}\leqslant 14\Delta^2$, where $n$ is the order of $G$, $\delta(G)$ is the minimum degree of $G$, and $\Delta(G)$ is the maximum\linebreak degree of $G$.
- vertex-distinguishing edge chromatic number /
- vertex-distinguishing star edge chromatic number /
- probability method

HTML全文

参考文献(1)

[1]

{1} GUILLAUME F, BRUCE R. Star coloring of graphs[J].

Journal of Graph Theory, 2004, {47(3)}: 163-182.
{2} LIU X S, DENG K.

An upper bound on the star edge chromatic index of graphs

with $\Delta\geqslant 7$[J]. Journal of Lanzhou University,

2008, {44(2)}: 98-100.
{3} CRISSTINA B, AMEL H B, Li H.

On the vertex-distinguishing proper edge-colorings[J].

Journal of Combinatorial Theory Series B,

1999, {75(2)}: 288-301.
{4} BURIS A C, SCHELP R H.

Vertex-distinguishing proper edge colorings[J]. Journal of Graph Theory,

1997, {26(2)}: 74-82.
{5} ALON, SADAKOV B, ZAKS A.

Acyclic edge coloringa of graphs[J]. Journal of Graph

Theory, 2001, 37: 157-167.
{6} RAHUL M, NARAYANAN N, SUBRAMANIAN C R.

Improved bounds on acyclic edge clouring[J]. Discrete Mathematics,

{2007, 307: 3063-3069}.
{7} MICHAEL M, BRUCE R.

Graph Coloring and the Probabilistic Method[M]. New York:

Springer-Verlag, 2002.
{8} BONDY J A, MURTY U S R.

Graph Theory with Applications[M]. New York: Macmillan Press Ltd,

1976.
{9} ALON N, SPENCER J.

The Probabilistic Method[M]. New York: John

Wiley and Sons, 1992.
{10} LIU X S, ZHU Z Q.

An Upper Bound on the Vertex-Distinguishing IE-Total

Chromatic Number of Graphs[J]. Journal of Shandong University,

2009, {44(10)}: 14-16.
{11}LIU X S, AN M Q, GAO Y.

An upper bound for the adjacent vertex-distinguishing total

chromatic number of a graph[J]. Journal of Mathematical Research \&

Exposition, 2009, {29(2)}: 343-348.
{12} LIU X S, WEI Z Y.

An upper bound for the vertex-distinguishing acyclic edge

chromatic number of graphs[J]. Journal of Lanzhou University, 2010,

{46(5)}: 75-78.

施引文献

资源附件(0)

访问统计