若干图的倍图的邻点可区别边(全)染色  

Adjacent vertex-distinguishing edge/total colorings of double graph of some graphs

作　　者：何雪[1] 田双亮[1] 

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

出　　处：《山东大学学报（理学版）》2015年第4期63-66,共4页Journal of Shandong University(Natural Science)

基　　金：西北民族大学研究生科研创新项目(ycx14146);西北民族大学科研创新团队计划资助

摘　　要：设G是具有顶点集V(G)和边集E(G)的简单图。如果G的一正常边染色σ满足对任意uv∈E(G),有Cσ(u)≠Cσ(v),其中Cσ(u)为点u的关联边所染颜色构成的集合,则称σ为G的邻点可区别边染色。如果G的一正常全染色σ满足对任意uv∈E(G),有Sσ(u)≠Sσ(v),其中Sσ(u)表示点u及u的关联边所染颜色构成的集合,则称σ为G的邻点可区别全染色。图G的邻点可区别边(或全)染色所需的最少的颜色数,称为G的邻点可区别边(或全)色数,并记为χ'as(G)(或χat(G))。给出了图G的倍图D(G)的以上两个参数的上界,并对完全图与树,确定了它们的倍图的邻点可区别边色数与全色数的精确值。Let G be a simple graph with vertex set V（ G） and edge set E（ G）. An edge-coloring σ of G is called an adjacent vertex distinguishing edge-coloring of G if Cσ（ u） ≠Cσ（ v） for any uv∈E（ G）,where Cσ（ u） denotes the set of colors of edges incident with u. A total-coloring σ of G is called an adjacent vertex distinguishing total-coloring of G if Sσ（ u） ≠Sσ（ v） for any uv∈E（ G）,where Sσ（ u） denotes the set of colors of edges incident with u together with the color assigned to u. The minimum number of colors required for an adjacent vertex-distinguishing edge-coloring（ resp.total-coloring） of G is called adjacent vertex-distinguishing edge（ resp. total） chromatic number,and denoted byχ＇as（ G）（ resp. χat（ G））. The upper bounds for these parameters of the double graph D（ G） of graph G are given in this paper. Specifically,the exact value of these parameters for the double graph of complete graphs and trees are determined.

关 键 词：倍图 邻点可区别边染色 邻点可区别全染色 

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