三部图K(m,n,r)-A(|A|=2)的色唯一性  

On the Chromatic Uniqueness of Tripartite Graphs K(m,n,r)-A(|A|=2)

作　　者：李凤琴[1] 

机构地区：[1]内蒙古大学数学系,呼和浩特010021

出　　处：《内蒙古大学学报（自然科学版）》2007年第2期121-126,共6页Journal of Inner Mongolia University：Natural Science Edition

摘　　要：设G是简单图,用P(G,λ)表示图G的色多项式,令K(m,n,r)表示完全三部图.证明了1)当3mnr时,令s=16(n-m)2+(r-n)2+(r-m)2+12,若m+n+r>23s+3s2,则K(m,n,r)-A(A=2)是色唯一图;2)当m4时,K(m,m,m)-A,K(m,m,m+1)-A,K(m,m+1,m+1)-A,(A=2)都是色唯一图;3)设n,k为非负整数,则当n>k2+23k2+6+k+2时,K(n-k,n,n)-A;当n>k2+2k2+6-k3+2时,K(n,n,n+k)-A;当n>233k2+6+k2+2时,K(n-k,n,n+k)-A(A=2)均为色唯一图.Let G be a simple graph,P（G,λ） denote the chromatic polynomial of G and let K（m, n,r） denote the complete tripartite graph. It is proved that 1） If 3≤m≤n≤r,let s=1/√6√（n-m）^2＋（r-n）^2＋（r-m）^2＋12if m＋n＋r〉2√3s＋3s^2,graphs K （m, n, r） - A （ ｜ A ｜ = 2） are chromatically unique ; 2） If m≥4 ,graphs K（m ,m ,m）--A,K（m ,m ,m＋1）-A ,K（m ,m＋1 ,m＋1）-A, （ ｜ A｜ = 2）are all chromatically unique; 3） Let n,k be non-negative integers,if n （k^2＋2√k^2＋6＋k）/3＋2K（n-k,n,n）-A;if n〉（k^2＋2√K^2＋4-k）/3＋2,K （n,n,n＋k）-A;ifn〉（2√3k^2＋6）/3＋k^2＋2K（n-k,n,n＋k）-A （｜A｜ =2）are all chromatically unique graphs.

关 键 词：三部图 色多项式 色唯一 色划分 

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