关于积图点可区别边染色的若干结论  

Some conclusions of vertex-distinguishing edge coloring of product graph

作　　者：马刚[1] 马效敏[2] 冶建华[1] 马少仙[1] 

机构地区：[1]西北民族大学数学与计算机科学学院,兰州730124 [2]西北民族大学科研处,兰州730030

出　　处：《运筹学学报》2013年第3期108-114,共7页Operations Research Transactions

基　　金：国家自然科学基金(No.61163037);西北民族大学中央高校基本科研业务费专项资金(No.ZYZ2011082);西北民族大学中青年科研基金(No.X2007-012)

摘　　要：如果图G的一个正常边染色满足任意两个不同点的关联边色集不同,则称为点可区别边染色(VDEC),其所用最少颜色数称为点可区别边色数.利用构造法给出了积图点可区别边染色的一个结论,得到了关于积图点可区别边色数的若干结果,并且给出25个具体积图的点可区别边色数,验证了它们满足点可区别边染色猜想(VDECC).A proper edge coloring of graph G is called vertex-distinguishing if the set of colors meets to vertex u differs from the set of colors meets to vertex v for any two distinct vertices u and v. The minimum number k for which there exists vertex distinguishing proper edge coloring using k colors is called the vertex distinguishing proper edge chromatic number. In this paper, we will obtain a conclusion of vertex-distinguishing edge coloring of product graph by using the method of construction, and get some results of the vertex-distinguishing edge chromatic numbers of product graphs, then obtain vertex-distinguishing edge chromatic numbers of 25 product graphs, which satisfy the conjecture on VDECC.

关 键 词：积图 联图 点可区别边染色 点可区别边色数 

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