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

A Note the Conjecture of Vertex-Distinguishing Edge Coloring of Graphs

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

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

出　　处：《数学的实践与认识》2010年第2期223-226,共4页Mathematics in Practice and Theory

基　　金：国家自然科学基金(10771091);宁夏大学科学研究基金((E)ndzr09-15)

摘　　要：图G的一个k-正常边染色f被称为点可区别的是指任意两点的点及其关联边所染色集合不同,所用最少颜色数被称为G的点可区别边色数,张忠辅教授提出一个猜想即对每一个正整数k≥3,总存在一个最大度为△(G)=k≥3的图G,图G一定有一个子图H,使得G的点可区别的边色数不超过子图的.本文证明了对于最大度△≤6时,猜想正确.A proper edge coloring of a simple graph G is called vertex distinguishing if for any two distinct vertices u and v in G, 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 Xvd（G）. Professor Zhang Zhongfu presented a Conjecture： For k = 3, 4, … , there always exists a graph G such that A（G） = k, and there is a subgraph H of G, it usable X＇vd（H） 〉 X＇vd（G）. In this paper, we proved the conjecture is ture for A ≤ 6.

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

分 类 号：O157.5[理学—数学] O156.1[理学—基础数学]