论文部分内容阅读
设P(G,λ)是图的色多项式,如果两个图G和H的色多项式相同(P(G,λ)=P(H,λ)),则称两个图是色等价的,记为G~H.如果与图G色等价的图H都与图G同构(G≌H),则称图G是色唯一图(或称图G是色唯一的).至1978年由Chao和Whitehead首次提出色唯一性的概念以来,完全t部图的色唯一性问题一直是人们讨论的课题.KohKM和TeoKL在文献[The search for chromatically unique graphs[J]. Graphsand Combinatorics,1990,6:259-285.KOHKM,TEOKL.The search for chromatically unique graphs-Ⅱ[J].Discrete Mathematics,1997(172):59-78.]中,综述了1990年和1997年以前的成果和正在研究的问题,对于完全t部图,其中给出了较著名的问题A(当jni-n≤2(i,j=1,2,L,),min{n1,n2,L,nt}充分大时,完全t部图K(n1,n2,Lnt)的是否是色唯一性图?)和在文献[Chia.G.L,Goh.B.HKoh.K.M.The chromaticity of some families of complete tripartite graphs. Scientia, SeriesA: Mathematical Sciences2,27-37(1988)]中提出的猜想B(若n3k+2,则三部图K(n-k,n,n)是色唯一图),这个问题和猜想在2004年发表的文献[ZhaoHaixing，LiXue-liang，LiuRu-ying,etal. The chromaticity of certain complete multipartite graphs[J]. Graphsand Combinatorics,2004,20:423-434; 和LiuRuyin,ZhaoHalxing,Ye Cheng-fu.Acomplete solution to a conjecture on chromalicuni queness of complete tripartite graphs[J]. Discrete Mathematics,2004,289:175-179.]中给出了解答,他们证明了如果|ni-nj|≤k(i,j=1,2,L,)，（公式略）,则K(n1,n2,…,nt)是色唯一图；如果n≥k+2≥4,则三部图K(n-k,n,n)是色唯一图；如果n≥2k≥4,则K(n-k,n-1,n)是色唯一图.在文献[Su Ke Yi,Chen Xiang En.A note on chromatic uniqueness of completely tripartite graphs[J]. Journal of Mathematical Research&Expsition，2010,30(2):233-240.]中,SuKeYi和ChenXiang En证明了若n≥(k2+v2+vk+v-k+4)/3,v≥2,k≥0,则完全三部图)K(n-v,n,n+k)是色唯一的.并给出了猜想C:设v=0,k≥4,或v=1,k≥3,若n≥(k2+v2+vk+v-k+4)/3,则完全三部图)K(n-v,n,n+k)是色唯一的.在文献[LAU.G.C,PENG.Y.H.Chromatic uniqueness of certain complete tripartite graphs[J].Acta Mathematica Sinica,EnglishSeries,2011,27(5):919-926.]中,LAU.G.C和PENG.Y.H.证明了若2≤v≤4,1=3k2/4+v+,则完全三部图K(n-k,n-v,n)是色唯一的.并给出了猜想D:若k≥v≥2 n≥k2/4+v+1,则完全三部图K(n-k,n-v,n)是色唯一的.在这里计算与估计了图的三角形子图和无弦四边形子图的计数,通过比较两个色等价图的t+1色类的划分数、三角形子图的个数、无弦的四边形子图的个数,证明了以下结果:若min{n+a1,n+a2,…,n+a,}≥1/2(公式略)，则K(n+a1,n+a2,…,n+a,)是色唯一图,其中n+ai是正整数;如果n>(k-1)2/4,且4≤v≤k≤2v,则完全三部图)K(n,n+v,n+k是色唯一的;如果k>2,n>(k+1)2/4+1,则完全t部图K(n-k,n-2,n,…,n)是色唯一的,等。