关于图的点可区别边染色的一个猜想

A Conjecture of Vertex-Distinguishing Edge Coloring of Graphs

图G的一个k-正常边染色f被称为点可区别的是指任意两个不同点的点及其关联边所染色集合不同,所用最少染色数被称为G的点可区别边色数,张忠辅教授提出一猜想即对每一个正整数k≥3,总存在一个最大度为△(G)=k≥3的图G,,满足图G一定有一个子图H,且母图的点可区别的边色数小于子图的.本文证明了对于最大度小于9时,此猜想正确.

A proper edge coloring of a simple graph G is called vertex distinguishing if for any two distinct vertices u and v inG,the set of colors assigned to the edges incident to u differs from the set of colors incident to v.The minimal number of colors required for a vertex distinguishing edge coloring of G is denoted by χ＇_（vd）（G）.Professor Zhang Zhongfu presented a Conjecture：For k =3,4,…,there always exists a graph G such that Δ（G） = k,and there is a subgraph H of G,it usable χ＇_（vd）（H） χ＇_（vd）（G）.In this paper,we proved the conjecture is true for Δ9.