图的点可区别无圈边色数的一个上界(英文)

图G的一个正常边染色f,若满足:1)G中无2-色圈;2)对于V(G)中的任意两点u和v,有C(u)≠C(v),这里C(u)={f(uw)|uw∈E(G)},则f叫做图G的一个点可区别无圈边染色.图G的点可区别无圈边色数,记为χ′_(vda)(G),是图G的一个点可区别无圈边染色所用色的最小数目.证明了若图G是一个最小度不小于5,且顶点数不超过30Δ~4的图时,χ′_(vda)(G)≤10Δ~2,其中Δ是图G的最大度.

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

If a proper edge coloring f of graph G satisfies:1)there is no 2-colored cycle in G;2)for any two distinct vertices u and v of V(G),we have C(u)≠ C(v),where C(u)= {f(uw)| uw ∈ E(G)},then f is called a vertex-distinguishing acyclic edge coloring of graph G.The vertex-distinguishing acyclic edge chromatic number of G,denoted by X'vda(G)is the minimal number of colors in a vertex-distinguishing acyclic edge coloring of G.It was proved that if G(V,E)is a graph with δ≥ 5,and n ≤ 30Δ4,then X'vda(G)≤ 10Δ2,where n is the order of G and δ(G)the minimum degree of G,and Δ(G)the maximum degree of G.