关于图的Grundy着色  

On Grundy Colorings of Graphs

作　　者：徐保根[1] 

机构地区：[1]华东交通大学基础科学学院,江西南昌330013

出　　处：《华东交通大学学报》2010年第1期78-81,共4页Journal of East China Jiaotong University

基　　金：国家自然科学基金项目(10661007);江西省自然科学基金项目(2007GZS0715);江西省教育厅科学研究项目(GJJ09215)

摘　　要：设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色数。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.

关 键 词：着色 色数 Grundy着色 Grundy色数 

分 类 号：O157.5[理学—数学]