论文部分内容阅读
为了攻克四色问题,1912年Birknoff在文献中介绍了关于映射M的色多项式,记为P(M,λ),它是在映射M下的正常λ-色数.如果能够证明对于所有的映射M都有P(M,4)>0,这就对四色问题给出了一个肯定的回答.图G的一个七顶点着色是指k种颜色1,2,…,k对于G的各顶点的-个分配；称着色是正常的,如果两个相邻的顶点都分配到不同的颜色.无环图G的-个正常k顶点着色是把V分成k个(可能有空的)独立集的一个分类(V1,V2,…,Vk).当G有-个正常k顶点着色时,就称G是k顶点可着色的(简称为k可着色).G的色数x(G)是指使G为k可着色的数七的最小值；若x(G)=k,则称G是k色的.
图G的色多项式就是至多用入种颜色对图G进行正常着色所有可能的不同的方法数,记作P(G,λ).对于-个正整数r,V(G)的-个分划(A1,A2,…,Ar)就叫做图G的-个r独立分划,如果Ai是图G的非空独立集.α(G,r)表示V(G)的r独立分划数,那么G的色多项式可以写成:这里(λ)i=λ(λ-1)(λ-2)…(λ-i+1).
如果P(G,λ)=P(H,λ),则图G和H是色等价的,记为G～H.用表示与G色等价的所有图组成的图族.1978年,Chao和Whitehead在文献中定义了-个图是色唯一的如果没有其它图与它具有相同的色多项式.即:如果与图G色等价的图都与G同构,则称图G是色唯一的.
本文主要利用色等价与色唯一的性质以及伴随等价和伴随唯一的性质来研究在完全三部图K(n,n,n)中删去s条边所得的三部图G=K(n,n,n)-S的色性.给出了三部图K(n,n,n)-S中具有较小4独立集数和较大4独立集数图的色性.利用本文方法可以研究完全t部图中删去s条边后得到的图的色性.