内蒙古大学学报（自然科学版）
內矇古大學學報（自然科學版）
내몽고대학학보（자연과학판）
ACTA SCIENTIARUM NATURALIUM UNIVERSITATIS NEIMONGOL
2004年
5期
485-489
,共5页
色多项式%色唯一性%完全4部图%伴随多项式
色多項式%色唯一性%完全4部圖%伴隨多項式
색다항식%색유일성%완전4부도%반수다항식
chromatic polynomial%chromatic uniqueness%complete 4-partite graphs%adjoint polynomial
设G是一个图,P(G,λ)是G的色多项式.若P(G,λ)=P(H,λ),则称G和H是色等价的,简单地用G～H表示.令[G]={H|H～G}.若[G]={G},称G是色唯一的.用G=K(n1,n2,n3,n4)表示完全四部图且2(<)n1(<)n2(<)n3(<)n4,得到了[G](∪){K(x,y,z,w)-S|x+y+z+w=n1+n2+n3+n4,1(<)x(<)y(<)z(<)w(<)n4-1,或1(<)x(<)y(<)z(<)n3-1和w=n4}(∪){G},其中S是K(x,y,z,w)的某s条边组成的集合且K(x,y,z,w)-S表示从K(x,y,z,w)中删去S中所有边得到的图.从而证明了当n(>)k+2,k(>)2时,K(n-k,n,n,n)是色唯一的.
設G是一箇圖,P(G,λ)是G的色多項式.若P(G,λ)=P(H,λ),則稱G和H是色等價的,簡單地用G～H錶示.令[G]={H|H～G}.若[G]={G},稱G是色唯一的.用G=K(n1,n2,n3,n4)錶示完全四部圖且2(<)n1(<)n2(<)n3(<)n4,得到瞭[G](∪){K(x,y,z,w)-S|x+y+z+w=n1+n2+n3+n4,1(<)x(<)y(<)z(<)w(<)n4-1,或1(<)x(<)y(<)z(<)n3-1和w=n4}(∪){G},其中S是K(x,y,z,w)的某s條邊組成的集閤且K(x,y,z,w)-S錶示從K(x,y,z,w)中刪去S中所有邊得到的圖.從而證明瞭噹n(>)k+2,k(>)2時,K(n-k,n,n,n)是色唯一的.
설G시일개도,P(G,λ)시G적색다항식.약P(G,λ)=P(H,λ),칙칭G화H시색등개적,간단지용G～H표시.령[G]={H|H～G}.약[G]={G},칭G시색유일적.용G=K(n1,n2,n3,n4)표시완전사부도차2(<)n1(<)n2(<)n3(<)n4,득도료[G](∪){K(x,y,z,w)-S|x+y+z+w=n1+n2+n3+n4,1(<)x(<)y(<)z(<)w(<)n4-1,혹1(<)x(<)y(<)z(<)n3-1화w=n4}(∪){G},기중S시K(x,y,z,w)적모s조변조성적집합차K(x,y,z,w)-S표시종K(x,y,z,w)중산거S중소유변득도적도.종이증명료당n(>)k+2,k(>)2시,K(n-k,n,n,n)시색유일적.
Let G be a graph and P(G,λ) the chromatic polynomial of G.Graphs G and H are said to be chromatically equivalent,simply denoted by G～H,if P(G,λ)=P(H,λ).Let [G]={H|H～G}.Graph G is said to be chromatically unique if [G]={G}.We denote by K(n1,n2,n3,n4) complete 4-partite graphs with 2(<)n1(<)n2(<)n3 n4.Let G K(n1,n2,n3,n4),we obtain that [G]{K(x,y,z,w)-S|x+y+z+w=n1+n2+n3+n4,1(<)x(<)y(<)z(<)w n4-1,or 1(<)x(<)y(<)z(<)n3-1 and w=n4}∪{G},where S is a set of some s edges of K(x,y,z,w) and K(x,y,z,w)-S denotes the graph obtained from K(x,y,z,w) by deleting all edges in S.Moreover we show that for any n(>)k+2 and k(>)2,K(n-k,n,n,n) is chromatically unique.
