关于图的Grundy着色

设G=(V,E)为一个图,函数f:V→{1,2,…,k}被称为图G的一个Grundyk-着色函数,如果f为图G的一个真k-着色函数且对于任何两种颜色i和j(1≤i≤j≤k),每个j色点的邻域中至少有一个i色点。图G的Grundy色数定义为Γ(G)=max{k|存在图G的Grundyk-着色函数}。给出了图的Grundy色数的若干上界,并确定了几类特殊图的Grundy色数。

On Grundy Colorings of Graphs

Let G = （ V, E）be a graph,a function f： V→{ 1,2,…, k}is said to be a Grundy k-coloring function of G. If f is a proper k-coloring of vertices in G such that for any two colors i and j （ 1 ≤ i ≤ j ≤ k ）, the neighborhood of any vertex with color j contains a vertex with color i. The Grundy chromatic number of G is defined as Г （G） = max { k } there exists a Grundy k-coloring function f of G }. In this paper, we give some upper bounds for Grundy chromatic number of a graph, and determine the Grundy chromatic numbers for several classes of graphs.