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

图的染色理论是图论的一个重要研究领域,求解图的色数被认为是一个NP-hard问题。对简单连通图G(V,E),存在一个正整数k,使得映射fV(G)∪E(G)→{1,2,…,K},如果对？uv∈E(G),有f(u)≠f(uv),f(v)≠f(uv),且C(u)≠C(v),则称f是图G的点边邻点可区别全染色(又称为邻点可区别VE-全染色),而χatve(G)=min{k|k－VE－AVDTC},称为G的点边邻点可区别边色数(又称为邻点可区别VE-全色数),其中色集合C(u)={f(u)}∪{f(uv)|uv∈E(G)}。本文构造了两类冠图Cm·Sn和Cm·Pn,研究了两类冠图Cm·Sn和Cm·Pn的点边邻点可区别全染色。根据Cm·Sn和Cm·Pn的结构性质,用穷染递推的方法,得到了它们的相应色数,给出一种染色方案。