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

LIU Xin-sheng; LU Wei-hua

Issue 5

Sep. 2012

Turn off MathJax

Article Contents

Article Navigation > Journal of East China Normal University (Natural Sciences) > 2012 > (5): 120-126

LIU Xin-sheng, LU Wei-hua. An upper bound for the vertex-distinguishing star edge chromatic number of graphs[J]. Journal of East China Normal University (Natural Sciences), 2012, (5): 120-126.

Citation:

LIU Xin-sheng, LU Wei-hua. An upper bound for the vertex-distinguishing star edge chromatic number of graphs[J]. Journal of East China Normal University (Natural Sciences), 2012, (5): 120-126.

LIU Xin-sheng, LU Wei-hua. An upper bound for the vertex-distinguishing star edge chromatic number of graphs[J]. Journal of East China Normal University (Natural Sciences), 2012, (5): 120-126.

Citation:

LIU Xin-sheng, LU Wei-hua. An upper bound for the vertex-distinguishing star edge chromatic number of graphs[J]. Journal of East China Normal University (Natural Sciences), 2012, (5): 120-126.

PDF( 197 KB)

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

Received Date: 2011-10-01
Rev Recd Date: 2012-02-01
Publish Date: 2012-09-25

Abstract

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

FullText(HTML)

References(1)

References

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

Relative Articles

Supplements(0)

Cited By

Proportional views