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

A Conjecture of Vertex-Distinguishing Edge Coloring of Graphs

作　　者：王治文[1] 朱恩强[2] 文飞[2] 

机构地区：[1]宁夏大学数学计算机学院,宁夏银川750021 [2]兰州交通大学应用数学研究所,甘肃兰州730070

出　　处：《数学的实践与认识》2013年第20期130-133,共4页Mathematics in Practice and Theory

基　　金：国家自然科学基金(11261046;11061024;11261043);宁夏自然科学基金(NZ1154);宁夏大学自然科学基金(ndzr10-7)

摘　　要：图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.

关 键 词：子图 边染色 图的点可区别边染色 图的点可区别边色数 

分 类 号：O157.5[理学—数学]