路与完全图的笛卡尔积图和广义图K(n,m)的关联色数  

ON INCIDENCE CHROMATIC NUMBER OF P_N×K_M AND K(n,m)

作　　者：陈学刚[1] 陈东灵[1] 王淑栋 

机构地区：[1]山东科技大学应用数学与软件工程系,泰安271019

出　　处：《经济数学》2000年第3期45-50,共6页Journal of Quantitative Economics

摘　　要：RichardA .Brualdi和J .QuinnMassey在 [1]中引入了图的关联着色概念 ,并且提出了关联着色猜想 ,即 :每一个图G都可以用Δ(G) +2种色正常关联着色 .B .Guiduli[2 ]说明关联着色的概念是I.Algor和N .Alon[3]提出的有向星荫度的一个特殊情况 ,并证实 [1]的关联着色猜想是错的 ,给出图G的关联色数的一个新的上界是Δ(G) +O(Log(ΔG) ) .[4 ]确定了某些特殊图类的关联色数 .本文给出了路和完全图的笛卡尔积图的关联色数 ,而且利用此结果又确定了完全图Kn 的广义图K(n ,m)Richard A.B rualdi and Jennifer J.Quinn Massey defined the incidence coloring in [1] and confectured: every graph can be incidence colored with △(G)+2 colors.B. Guiduli [2] showed that the concept of incidence coloring is a special case of directed star arboricity, introduced by I.Algor and N.Alon [3] and proved that the conjecture in [1] is false. According to a tight upper bound for directed star arboricity, he gave an upper bound for incidence coloring number, namely; Inc(G)≤△+O(log△), where △=△(G). chen etc.determined the incidence coloring number of some special graphs in [4]. In this paper, we give the incidence chromatic number of cartesian product of path and complete graph. According to the result we give the incidence chromatic number of K(n,m).

关 键 词：笛卡尔积 关联着色 广义图 路 完全图 关联色数 

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