图簇Sδ^G的补图的色等价图的结构性质

通过研究Sδ^G型图簇的伴随多项式的因式分解，证明了这类图簇的补图的色等价图的结构性质和非色唯一性。     

图簇S_δ~G的补图的色等价图的结构性质

通过研究SGδ型图簇的伴随多项式的因式分解,证明了这类图簇的补图的色等价图的结构性质和非色唯一性。     

两类E~G形图簇的补图的色等价性定理

设G是任意的p阶连通图,用ΨG(i)(k,p)表示把图G的第i个顶点vi与星图Sk+1的k度点重迭后得到的图(1≤i≤p),给出了图ΨG(i)(k,p)与星图Sn+1组合而成的两类EG形图簇,并通过研究这些图簇的伴随多项式的因式分解,进而证明了它们的补图的色等价性定理。     

若干图的伴随分解及色等价性

设Pm和Cm分别表示具有m个顶点的路和圈,G是任意的r阶连通图,设m是正奇数,把路Pm的标号为奇数的2-1(m+1)个顶点分别与2-1(m+1)G每个分支的第i个顶点Vi重迭后所得到的图记为ρG(i)m+2-1(m+1)r。运用图的伴随多项式的性质,首先给出了一类图簇ρG(i)(2 m+2)+((m+1)r的伴随多项式。进而令m=2t-1 q-1,λn=(2nq-1)+2n-1 qr,在讨论上述图的伴随多项式的基础上,我们证明了图ρG(i)λt和ρG(i)λt∪(t-1)K1的伴随多项式的因式分解定理,进而证明了这些图类的补图的色等价性。     

一类VSλδ形图簇的伴随分解定理及其补图的色等价性

设Pn是具有n个顶点的路,Sδ表示有δ=r+1个顶点的星图,把Pn的n个顶点与nSδ的每一个分支的r度顶点依次重迭后得到的图记为PSλδ,并用VS(kn+1)δ表示kPSnδ的每个分支的一个r+1度点与星图Sr+k+1的k个1度点依次重迭后得到的图.运用图的伴随多项式的性质,讨论图簇VS(kn+1)δ∪(k-1)Sδ的伴随多项式的因式分解定理,进而证明了它们的补图的色等价性.     

一类w_(λδ)~S形图簇的伴随分解定理及其补图的色等价性

设Pn是具有n个顶点的路,Sδ表示有δ=r+1个顶点的星图,把Pn的n个顶点与nSδ的每一个分支的r度顶点依次重迭后得到的图记为PSnδ,用wS(kn+1)δ表示kPSnδ的每个分支的两个r+1度点与星图S2k+r+1的2k个1度点依次重迭后得到的图,运用图的伴随多项式的性质,讨论了当n=2tq-1≥2时,两类图簇wS(kn+1)δ∪(2k-1)Sδ的伴随多项式的因式分解定理,进而证明了它们的补图的色等价性。     

S-桥图的色惟一性

由连接两个项点的s条内部不交的路组成的图中s－桥图，记作F（k1,k2,…ks）本文讨论了此类图的色性，给出了此类图色借书证一的一个充分条件，并证明了s- 2－桥图Ft(2,2,…，2，a,b）是色惟一的。     

广义树及其应用

本文提出广义树、树序列等概念。树、完全图、ｑ－树都是广义树的特例。由于广义树的色多项式容易求得，利用删边－粘点公式可以求一般图的色多项式；广义树的点色数等于它包含的最大点团所含点数，因此利用广义树求一般图的点色数也是一种可行的算法。     

Y(4,λ)形图簇的伴随多项式的分解及其补图的色等价性

设Pn和Cn是具有n个顶点的路和圈,Sn是n个顶点的的星图,nG表示n个图G的不相交并。EG(r+1)p+r表示把星Sr+1的r个1度点分别与rG的每个分支的第i个顶点重迭,同时把Sr+1的r度点与另一个G的第i个顶点重迭后得到的图,可简记为EGδ,δ=(r+1)(p+r);设m是自然数,图PEG(2 m+1)+(m+1)δ是表示把(m+1)EGδ的每个分支的r+di度顶点分别与P2 m+1的下标为奇数的m+1个顶点重迭后得到的图,记λ=(2 m+1)+(m+1)δ,图Y(4,λ)表示把PEG(2 m+1)+(m+1)δ的两个r+di+1度点与2P3的两个2度点重迭后得到的图,运用图的伴随多项式的性质,讨论了图簇Y(4,λ)∪K1(m为奇数)和Y(4,λ)∪EGδ(m为偶数)的伴随多项式的因式分解式,令m=2k-1 q-1,λk=(2kq-1)+2k-1 qδ,讨论了图簇Y(4,λk)∪(k-1)K1和Y(4,λk)的伴随多项式的因式分解式,进而证明了这些图的补图的色等价性。 更多还原     

图簇Gj1j2…jt^S^＊（i）（p,tkm）的伴随多项式的因式分解及色性分析

令S1，k表示k＋1个顶点的星，Pm表示m个顶点的路，G是任意的p阶连通图，设V（Pm）={V1，V2，…，Vm-1，Vm}及相应的度序列为（1，2，…，2，1）。S2km＋1^p（i）表示把kPm的每个分支的第i个顶点Vi分别与星S1,k的k个1度点重迭后得到的图，用Gj1j2…ji^S^＊（i）（p，tkm）表示把tSkm＋1^P（i）的每个分支的k度点分别与图G的顶点uj1，uj2，ujt，ujl（t≤p）重迭后得到的图，这里p≥1，k≥2，m≥3，1≤i≤m，t≥1．我们通过讨论图簇Skm＋1^p（i）,U（k-1）K1、S2rm＋1^P（i），S（2r-1）m＋1^P（i）以及Gj1j2…jt^S＊（i）（p，2rmt），Gj1j2……jt^S＊（i）（2r-1）mt）的伴随多项式的因式分解，证明了它们的补图的色等价图的结构定理，推广了张秉儒证明的文[8]中的定理2和定理4。     

关于图的色唯一性的若干结果

给出了不连通图和含割点的连通图为色唯一的充分必要条件，同时给出了２－连通图是色唯一的一个必要条件以及相应的一些结果。     

图Ψ*S*（4δ,nδ）∪tSδ*的伴随多项式的分解及色等价性分析

设Pn是具有n个顶点的路,Ψ*(4,n)表示把2P3的两个2度点分别与Pn的两个1度点重迭后得到的图,Sδ*(δ=rm+1)表示把rPm+1的每个分支的一个1度点重迭在一起得到的图。用PnSδ*表示把Pn的n个顶点与nSδ*的每一个分支的r度顶点依次重迭后得到的图,并用Ψ*S*(4δ,nδ)表示把图Ψ*(4,n)的n+4个顶点与(n+4)Sδ*的每一个分支的r度顶点依次重迭后得到的图。运用图的伴随多项式的性质,证明了图PnSδ*∪tSδ*与Ψ*S*(4δ,nδ)∪tSδ*的伴随多项式的因式分解定理,进而得到了这类图的补图的色等价图的结构特征。     

图簇GS*(i)j1j2…jt(p,tkm)的伴随多项式的因式分解及色性分析

令S1,k表示k+1个顶点的星,Pm表示m个顶点的路,G是任意的p阶连通图.设V(Pm)={V1,V2,…,Vm-1,Vm}及相应的度序列为(1,2,…,2,1).SP(i)km+1表示把kPm的每个分支的第i个顶点Vi分别与星S1,k的k个1度点重迭后得到的图,用GS*(i)j1j2…jt(p,tkm)表示把tSP(i)km+1的每个分支的k度点分别与图G的顶点uj1,uj2,…,ujt(t≤p)重迭后得到的图,这里p≥1,k≥2,m≥3,1≤i≤m,t≥1.我们通过讨论图簇SP(i)km+1∪(k-1)K1、SP(i)2rm+1,SP(i)(2r-1)m+1以及GS*(i)j1j2…jt(p,2rmt),GS*(i)j1j2…jt(p,(2r-1)mt)的伴随多项式的因式分解,证明了它们的补图的色等价图的结构定理.推广了张秉儒证明的文[8]中的定理2和定理4.     

Y2,2,λ*形树的伴随多项式的分解及其补图的色等价性

设Pn和Cn是具有n个顶点的路和圈,nG表示n个图G的不相交并。令S*r（m+1）+1表示rPm+2的每个分支的一个1度点重迭后得到的图,■表示把Pm的一个1度点与S*r（m+1）+1的r度点重迭后得到的图,可简记为■,δ=（r+1）m+r;设n（≥3）是奇数,λ=n+2-1（n+1）δ,图■表示把■的每个分支的r+1度顶点分别与Pn的下标为奇数的2-1（n+1）个顶点重迭后得到的图,Y*（2,2,2λ+1）表示把■的两个r+2度点分别与2P3的两个2度点重迭后得到的图,运用图的伴随多项式的性质,讨论了图簇■和■的伴随多项式的因式分解式,令n=2k-1q-1,λk=（2kq-1）+2k-1qδ,讨论了图簇Y*（2,2,λk）∪K1和Y*（2,2,λk）∪（k-1）K1的伴随多项式的因式分解式,进而证明了这些图的补图的色等价性。     

关于图θ（a,b,c,d,e）的色性

在两个顶点之间用五条长分别是ａ，ｂ，ｃ，ｄ，ｅ的内部不交的路连接而形成的图记为θ（ａ，ｂ，ｃ，ｄ，ｅ），其中ａ≤ｂ≤ｃ≤ｄ≤ｅ，本文讨论了它的色性．得出了θ（ａ，ｂ，ｃ，ｄ，ｅ）是色唯一的一个充分条件．     

一类树的伴随多项式的分解及其补图的色等价性

设Pn和Cn是具有n个顶点的路和圈,nG表示n个图G的不相交并。令S*r（m+1）+1表示rPm+2的每个分支的一个1度点重迭后得到的图,E■表示把Pm的一个1度点与S*r（m+1）+1的r度点重迭后得到的图,可简记为E■,δ=（r+1）m+r;设n（≥4）是偶数,λ=（n+1）+2-1（n+2）δ,令图P■是表示把2-1（n+2）E■的每个分支的r+1度顶点分别与Pn+1的下标为奇数的2-1（n+2）个顶点重迭后得到的图,运用图的伴随多项式的性质,讨论了图簇E■∪rK1、P■∪E■和P■∪2E■∪rK1的伴随多项式的因式分解式,进而证明了这些图的补图的色等价性。     

V_xδω∪yω_δ形图簇的伴随分解及其补图的色等价性

设Pn和Cn分别是n个顶点的路和圈,用Sk*n+1表示把kPn+1的每个分支的一个1度点重迭在一起得到的图,ωδ(δ=rm+1)表示把rCm+1中每个分支的一个1度点重迭后得到的图,并用Vω(kn+1)δ表示把图Sk*n+1的kn+1个顶点与(kn+1)ωδ的每一个分支的2r度点依次重迭后得到的图。运用图的伴随     

图的色数的一个上界

本文给出了图的色数的一个新上界,它改进了文献[2]中定理1.8的结论.     

线团图的一些性质

B.Hedman在文[1]中介绍了构造线团图的一个算法.本文用这一算法得到了线团图的一些性质.它们涉及到图的连通度、直径和色数.     

关于色多项式根2的阶

研究了图和色多项式根2的阶之间的关系,给出了色多项式根2的阶为1的一些充分条件。