关于完全3部图的色唯一性

文章设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图;通过比较3部图的4色类的划分数证明,如果4≤v+2≤k≤2v,n>(k-1)2/4,则完全3部图K(n,n+v,n+k)是色唯一图。

关于完全t部图的色唯一性

设P(G,λ)是图的色多项式。如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称图G是色唯一图.这里通过比较t+1色类的色划分数目,讨论了由Koh和Teo在文献[1]中提出的问题(若|ni-nj|≤2,当min(n1,n2,…,nt)充分大时,完全t部图K(n1,n2,…,nt)是否是色唯一图?)。改进了文献[5]中的结果。证明了若Σ1≤i≤ta2i=T,min{n+a1,n+a2,…,nt+at,n-1}≥(T+1)/2,则K(n+a1,n+a2,…,n+at)是色唯一图(其中ai是实数,n+ai是正整数)。从而证明了若|ni-nj|≤k(i,j=1,2,…,t),min{n1,n2,…,nt}≥tk2/8+1,则K(n1,n2,…,nt)是色唯一图。

完全t部图K(n-k,n-2,n,…,n)的色唯一性

文章介绍了完全t部图K(n-k,n-2,n,…,n)的色唯一性,设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图,通过比较t部图的t+1色类的划分数和三角形子图的个数证明,如果n>[(k+1)2/4]+1,并且k>2,则完全t部图K(n-k,n-2,n,…,n)是色唯一图。

完全t部图的色唯一性

设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图;这里通过比较t部图的t+1色类的划分数,证明了若min1≤i≤t{n+ai}≥1/2(a12+a22+…+at2)-1/2t(a1+a2+…+at2)+1,则完全t部图K(n+a1,n+a2,…,n+at)是色唯一图;若n≥(t-1)/2t(k2+v2)+1/tkv+v+1,v≥0,k≥-v,则完全t部图K(n-v,n,n+k,n,…,n)是色唯一的。

关于E．Sampathkumar等人猜想的证明

该文证明了Ｅ．Ｓａｍｐａｔｈｋｕｍａｒ和Ｃ．Ｖ，Ｖｅｎｋａｔｃｈａｌａｍ的关于图与补图的色划分数的一个猜想．