Halin图的2-距离和可区别全染色

摘要

记[k]={1,2,…,k}为颜色集.设f:V(G)∪E(G)→[k]为图G的一个k-全染色.令■,其中,NG(u)表示u的邻点集.若对G中距离不超过2的任意两点u、v,有S(u)≠S(v),则称f为图G的一个2-距离和可区别k-全染色.图G的2-距离和可区别k-全染色中最小k值称为图G的2-距离和可区别全色数,记为■.该文运用组合零点定理证明了最大度至少为4的Halin图G满足■,其中,Δ(G)表示图G的最大度.

关键词

2-距离和可区别全染色 / Halin图 / 组合零点定理