2类特殊图的邻和可区别全染色

2类特殊图的邻和可区别全染色

李永艳

【摘 要】摘要：研究了图K和Dn,4的邻和可区别全染色．根据图K和Dn,4的结构特点，利用穷染的方法得到了图K和Dn,4的邻和可区别全色数． 【期刊名称】高师理科学刊 【年(卷),期】2017(037)004 【总页数】2

【关键词】穷染法；邻和可区别全染色；邻和可区别全色数

1 引言及预备知识

本文只对有限、无向、简单图进行讨论．设图G=(V(G),E(G))，分别用V(G)，E(G)，Δ(G)表示图G的顶点集、边集和最大度．

定义1[1]设图G是阶数不小于2的连通图，[k]={1,2,…,k}，φ是从V(G)UE(G)到[k]的映射，对于任意u∈V(G)，令，如果φ满足： （1）对于任意uv∈E(G)，有φ(u)≠φ(v)≠φ(uv)； （2）对于任意uv,uw∈E(G),v≠w，有φ(uv)≠φ(uw)．

则称φ为图G的正常[k]-全染色．若进一步满足：对任意的uv∈E(G)，有f(u)≠f(v)，则称φ为图G的 [k]-邻和可区别全染色，k的最小值称为图G的邻和可区别全色数，记为

定义2[2]1设图是由点集和边集所形成的图，该图称为风车图．

定义3[3]59由点集V(Dn,4)={v0,v11,v12,v13,v21,v22,v23,…,vn1,vn2,vn3}和边集所形成的图，记为Dn,4．

Pilsniak和Wozniak[1]研究了邻和可区别全染色，并提出猜想．