Halin图的2-距离和可区别全染色OA北大核心CSTPCD

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