摘要
设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(GH),则称图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.
基金
淮南职业技术学院科技基金项目(HKJ10-6)资助
关键词
完全三部图
色唯一性
三角形子图
四边形子图
complete tripartite graph
chromatic uniqueness
triangular subgraph
quadrangular subgraph
