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

对整数r0,图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的多彩色数χ_r(G)。本文主要研究在图G中删掉任意一个2度点后多彩色数的变化。

Studies on 2-vertex deletion issues in r-hued coloring of graphs

For a positive integer r, a r hued coloring of a graph G is a mapping c: VG→1,2,…, k, such that：(1) if u,v∈VGare adjacent vertices in G, then cu≠cv; (2) for any v∈ VG, cNv≥minNv,r.N(v) is the set of vertices which are adjacent to vertex v. The smallest integer k, which let G have a proper (k,r) coloring, is defined as r hued chromatic number χrG. In this paper, the differences between χrG-vand χrG (d(v)=2) which caused by 2 vertex deletion is investigated.