图多彩染色中的2度点删除问题

摘要

对整数r＞0,图G的一个r-多彩染色是一个从顶点集V(G)到数集[1,2,…,k}的映射c,使得:(C1)相邻点获得的颜色不同;(C2)| c(N(v))|≥min{ ｜N(v)｜,r}(其中N(v)代表v的邻点集).使图G有一个正常的(k,r)-染色的最小k值称为G的多彩色数xr(G).本文主要研究在图G中删掉任意一个2度点后多彩色数的变化.