两类冠图的点边邻点可区别全染色.pdfVIP

研究论文(Articles) 科技导报201 针巍= 1．29(27) 两类冠图的点边邻点可区别全染色 田京京 陕西理工学院数学系．陕西汉中723001 摘要图的染色理论是图论的一个重要研究领域。求解图的色数被认为是一个NP—hard问题。对简单连通图G(¨E)。存在一个正 整数k。使得映射，：ⅥG)uE(G)一(1，2，…，叼，如果对VUVE E(G))。本文构造了两类冠图C_·S和G·R，研究了两类冠图C『。· 邻点可区别VE-全色数)．其中色集合C(u)={IIU))u{f(uv)luw S和C_·R的点边邻点可区别全染色。根据Cm·S和G·只的结构性质，用穷染递推的方法，得到了它们的相应色数。给出一种染 色方案。 关t词冠图；点边邻点可区别全染色；点边邻点可区别边色数 中圈分类号0157．5 文献标识码A doI 1．27．008 10．39814．issn．1000—7857．201 TotalChromaticNumber Vertex-edgeAdjacentVertex—distinguishing oftheTwoKindsofCrown Graphs TIAN Jingjing DepartmentofMathematics，ShaanxiUniversityofTechnology,Hanzhong723001，ShaanxiProvince，China isoneofthechief inthe research．thesolutionofthechromaticnumberofthe isanNP- Ab翻嬲Graphcoloring topics graph graph hard bea isa a from thatV聊∈E problem．LetC(V，D simplegraph，kpositiveinteger．fismappingv(c)ug(c)to{l，2，…，k}such be can calledthe vertex total of (G)，thenflu)≠fluv)，Av)#jfIuv)，C(u)≠C(口)，fvertex—edge—adjacent distinguishingcoloringG(adjacent vertex VE-total of becalledthe vertex distinguishingcoloringG)，Xg(G)=min{klk—VE—AVDTC}wouldvertex-edge-adjacentdistinguishing totalchromaticnumberof vertex VE-totalchromaticnumberofG)，where veaex G(adjacentdistinguishing vertex-edge-adjacent total ofG E this kindsofcrown and distinguishingcoloringc(u)=仉u)lu(，Iuv)luvE(G)}：Inpaper,two G·Sn G·只are