完全三部图K(n-k,n-v,n)的色唯一性  

Chromatic uniqueness of complete tripartite graphs K(n-k,n-v,n)

作　　者：徐利民[1,2] 杨志林[1] 

机构地区：[1]合肥工业大学数学学院,安徽合肥230009 [2]淮南职业技术学院,安徽淮南232001

出　　处：《中国科学技术大学学报》2013年第3期190-196,201,共8页JUSTC

基　　金：淮南职业技术学院科技基金项目(HKJ10-6)资助

摘　　要：设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(GH),则称图G是色唯一图.文献[Lau G C,Peng Y H.Chromatic uniqueness ofcertain complete tripartite graphs.Acta Mathematica Sinica,English Series,2011,27(5):919-926]中提出一个猜想(若k≥v≥2,n≥k2/4+v+1,则完全三部图K(n-k,n-v,n)是色唯一的),并证明了若2≤v≤4,k≥v≥2,n≥k2/4+v+1,则K(n-k,n-v,n)是色唯一的.通过比较三角形子图和无弦四边形子图的个数,证明了若v≥4,k≥2v2+4,n≥(k+2)2/8+3,则K(n-k,n-v,n)是色唯一图。Let P（G,λ） be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H with P（G,λ）=P（H,λ） implies G=H. Lau and Peng [Lau G C, Peng Y H. Chromatic uniqueness of certain complete tripartite graphs. Acta Mathematiea Siniea, English Series, 2011,27 （5）： 919-926] brought forward a conjecture that K（n-k, n-v, n） is chromatically unique if k≥v≥2 and n≥ k^2/4 ＋ v＋ 1, and showed that K （n- k, n- v, n） is chromatically unique if ≥v≥4 and k≥v and n≥k^2/4 ＋ v＋1. By comparing the number of the triangular subgraphs and that of the quadrangular subgraphs without chords, it was shown that K（n-k,n-v,n） is chromatically unique for n≥（k＋2）^2/8＋3 and k≥ 2v^2 ＋4 and v≥4.

关 键 词：完全三部图 色唯一性 三角形子图 四边形子图 

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