The Chromaticity Of Certain Complete T-partite Graphs

Let P(G,λ) be the chromatic polynomial of a graph G. Two graphs are chromatically equivalent, symbolically G～H, if P(G,λ)=P(H,λ). A graph G is chromatically unique, if for any graph H with H～G implies G≌H. The notion of the chromatic uniqueness was first introduced by Chao and Whitehead in1978. Since then, the problems of chromatic uniqueness of the complete t-partite graphs still are studied. Koh K M and Teo K L have summarized achievements and problems that were studied before that in1990and1997in ref [Koh K M, Teo K L. The search for chromatically unique graphs[J]. Graphs and Combinatorics,1990,6:259-285; KOH K M, TEO K L. The search for chromatically unique graphs-Ⅱ [J].Discrete Mathematics,1997(172):59-78.]. Among them, the famous problem (for|n1-n1|≤2and i,j=1,2,…,t, if min{n1,n2,…,n1} is sufficiently, is the complete t-partite graph K(nl,n2,…nt) chromatically unique?) and the conjecture (The complete tripartite graph K(n-k,n,n) is chromatically unique if n≥k+2≥4.) have be solved in ref [Zhao Hai xing, Li Xue-liang, Liu Ru-ying, et al. The chromaticity of certain complete multipartite graphs [J]. Graphs and Combinatorics,2004,20:423-434; Liu Ruyin, Zhao Hal xing, Ye Cheng-fu. A complete solution to a conjecture on chromalic unique of complete tripartite graphs[J].Discrete Mathematics,2004,289:175-179.]. They proved that the complete tripartite graph K(n-k,n,n) is chromatically unique if n>k+2>4, and the complete tripartite graph K(n-k,n-1,n) is chromatically unique if n>2k>4, the compete t-partite graph K(n1,n2,…,nt) is chromatically unique for|ni-nj|≤k (i,j=1,2,…,) if min{n1,n2,…;nt}≥tk2/4+k√2(t-T1/2+1. In ref [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.], Su Ke Yi and Chen Xiang En showed that K(n-v,n,n+k) is chromatically unique for v≥2and k≥0if n≥3/1(k2+v2+kv+v-k+4),and they present a conjecture (Ifn≥3/1(k2+v2+kv+v-k+4), then K(n-v,n,n+k) is chromatically unique, where v=0and k≥4,orv=1and k≥3.). In ref [LAU.G.C, PENG.Y.H. Chromatic uniqueness of certain complete tripartite graphs[J].Acta Mathematica Sinica, English Series,2011,27(5):919-926.], LAU.G.C and PENG.Y.H showed that K(n-k,n-v,n) is chromatically unique for n≥4/1k2+v+1, where2≤v≤4and k≥v, they present a conjecture (If n≥4/1k2+v+1and k≥v≥2, the graph K(n-k,n-v,n) is chromatically unique.In the paper,by compa ring the number of triangles in graphs and the number of cycles of4一order without chords in graphs and the numbers of partition into t+1color classes,proved the following results. The complete t-partite graph K(n+α1,n+α2,…,n+αt) is chromatically unique if min{n+αa,n+α2,…,n+αt}≥2/1{∑1<i<t..,αi2-2t/1(∑1<i<t..,αi；)2+1;The complete tripartite graph K(n,n+v,n+k)is chromatically unique if n>(k-1)2/4and4≤v+2≤k≤2v; The complete t-partite graph K(n-k,n-2,…,n)is chromatically unique if n>2and n>(k+1)2/4+1,etc.