关于几类特殊图的Mycielski图的邻点可区别全色数(英文)

摘要

设G是一个简单图,f是一个从V(G)∪E(G)到{1,2,…,k}的映射.对每个v∈V(G),令Cf(v)={f(v)}∪{f(vw)|w∈V(G),vw∈E(G)}如果f是G的正常全染色且(?)u,v∈V(G),一旦uv∈E(G),就有Cf(u)≠Cf(v),那么称f为G的邻点可区别全染色(简称为k-AVDTC).设Xat(G)=min{k|G存在k-AVDTC},则称Xat(G)为G的邻点可区别全色数.给出了路、圈、完全图、完全二分图、星、扇和轮的Mycielski图的邻点可区别全色数.