关于完全三部图色唯一性的判定  

On Chromatic Uniqueness of Complete Tripartite Graphs

作　　者：唐凯[1] 郝荣霞[1] 徐兰栓 

机构地区：[1]北京交通大学理学院,北京100044 [2]邢台广播电视大学理工系,河北邢台054000

出　　处：《北京交通大学学报》2007年第6期64-68,共5页JOURNAL OF BEIJING JIAOTONG UNIVERSITY

摘　　要：G是简单图,用P(G,λ)表示图的色多项式.若对任意简单图H当P(H,λ)=P(G,λ)时,都有H■G,则称G是色唯一图.Liu R.,Zhao H.X.和Ye C.已经证明:当n和k为整数且满足n≥k+2≥4,完全三部图K(n-k,n,n)是色唯一的;当n和k满足n≥2k≥4时,完全三部图K(n-k,n-1,n)是色唯一的.在本文中,证明了当k是奇数且n≥k2/4+15/4≥6,或k是偶数且n≥k2/4+4≥5时,完全三部图K(n-k,n-2,n)是色唯一的;当k是奇数且n≥k2/4+19/4≥7,或k是偶数且n≥k2/4+5≥9时,K(n-k,n-3,n)是色唯一的.Let P（ G ,λ ） be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P（H,λ） = P（G,λ） implies H ≌ G. R. Liu, H. X. Zhao and C. Ye showed that the following complete tripartite graphs are χ -unique graphs： K（ n - k, n, n） for any integers n and k with n≥k＋2≥4;K（n- k,n-l,n）foranyintegersnand k with n ≥2k≥4. In this paper, we show that the following complete tripartite graphs are χ -unique graphs： K（ n - k, n - 2, n） for k is odd and n ≥ k^2/4＋ 15/4≥6, or k is even and n ≥ k^2/4＋4^5; K（n- k,n-3,n） forkis odd and n≥k^2/4 ＋ 19/4 ≥7, or k is even and n ≥ k^2/4 ＋ 5≥ 9.

关 键 词：图 色多项式 色唯一图 

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