完全四部图的色性

设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｜z y w =n1 n2 n3 n4,1≤z≤y≤z≤w≤n4-1，或1≤x≤y≤z≤n3-1和w=n4U{G}，其中S是K(x，y，z，w)的某s条边组成的集合且K(x，y，z，w)-s表示从K(x，y，z，w)中删去S中所有边得到的图．从而证明了当n≥k 2，t≥2时，K(n-k，n，n，n)是色唯一的．     

一类广义多边形树的色唯一性

讨论了5-桥图F（a,a,a,a,b）（2≤a＜b）的色性,并证明了此类图是色唯一的.     

关于完全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（1,2,n）∪（∪iCui）]补的色等价刻画

研究稠密图[T(1,2,n)∪(∪iCui)]补的色性，并刻画它的色等价图，其中，T（l1,l2,l3,)(l1≤l2≤l3）表示只有一个3点度，三个1度点，且唯一3度点到三个1度点的距离分别为l1,l2,l3的树，P（G，λ）和h(G,x)分别表示图G的色多项式和伴随多项式。     

P_n~k和T_((k_1,k_2,…,k_n))的色多项式

本文研究了图Pnk和T(k1,k2,…,kn)的色多项式,得到P2n、P3n和T(k1,k2,…,kn)的色多项式递推公式,以及Pn2仅当n≤4时是色唯一图,T(k1,k2,…,kn)仅当n=1是色唯一图等结论.     

Pkn和T(k1,k2,…,kn)的色多项式

本文研究了图Pkn和T(k1,k2,…,kn)的色多项式,得到P2n、P3n和T(k1,k2,…,kn)的色多项式递推公式,以及P2n仅当n≤4时是色唯一图,T(k1,k2,…,kn)仅当n=1是色唯一图等结论.     

具有5n+4个点的5部图的色性

设G是简单图，用P(G，λ)表示图G的色多项式，若P(G，λ)=P(H，λ)，则称G与H是色等价．令H～G，令{G}={H|H～G)，若对任意的图G有{G}={G}，称G是色唯一的．设G表示具有5n 4个点的完全5部图，令θ(G)=(m5(G)-2^n 2-2^n-1 5)／2^n-1，其中m5(G)表示G的6-独立分划个数．本文证明了θ(G)≥0且刻划θ(G)=0，1，3／2，2，5／2，13／4的图．利用此结果研究了图G—S的色性，其中S是图G某些边组成的集合，G—S表示从G中删去S中所有的边得到的图，进而得到许多色唯一的5部图．     

一类距离图的分数色数

摘要：主要讨论了距离图G(Z,D_{m,k,k+1,k+2,k+3})(其中D_{m,k,k+1,k+2,k+3}=｛1,2,…,m｝-｛k,k+1,k+2,k+3｝)的分数色数,以及当2k≤m≤2k+5时G(Z,Dm,k,k+1,k+2,k+3)的色数。     

稠密图T(1,2,n)∪(∪iCui)的色等价刻画

研究稠密图T(1,2,n)∪(∪iCui)的色性,并刻画它的色等价图.其中,T(l1,l2,l3)(l1≤ l2≤l3)表示只有一个3度点,三个1度点,且唯一3度点到三个1度点的距离分别为l1,l2,l3的树,P(G,λ)和h(G,x)分别表示图G的色多项式和伴随多项式.     

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

设G是简单图,用P(G,λ)表示图G的色多项式,令K(m,n,r)表示完全三部图.证明了1)当3≤m≤n≤r时,令s=1/√6√(n-m)2 (r-n)2 (r-m)2 12,若m n r＞2√3s 3s2,则K(m,n,r)-A(|A|=2)是色唯一图;2)当m≥4时,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 2√k2 6 k 2时,K(n-k,n,n)-A;当n＞k2 2√k2 6-k/3 2时,K(n,n,n k)-A;当n＞2√3k2 6 k2 2时,K(n-k,n,n k)-A(|A|=2)均为色唯一图.     

关于两类K4同胚图色等价性的研究

利用色多项式研究了围长为7的K4同胚图K4(1，3，3，δ，ε，η)与K4(3，2，2，δ′，ε′，η′)之间的色等价性问题，指出围长为7的K4同胚图K4(1，3，3，δ，ε，η)与K4(3，2，2，δ′，ε′，η′)不存在色等价关系。这一结论有助于解决围长为7的K4同胚图的色唯一性问题。     

5—桥图的色唯一性

由连接两个顶点的S条内部不交的路组成的图叫S－桥图。本文证明了一类5－桥图F（1，2，2，a,b)（a≥b≥3）是色唯一的。     

最大度为4的外平面图的无圈边色数

一个图G的无圈边染色是一个正常的边染色,使得任一个圈上至少有3种不同的颜色.G的无圈边色数a＇（G）是使得G有无圈k-边染色的最小整数k.设G是一个最大度为4的外平面图.对于现有结果 4≤a＇（G）≤5中,何时为4,何时为5,还没有一个完整的刻画.给出一个使得a＇（G）=4的充分条件,拓展了该领域的相关结果.     

二部图 K(m,n)-A(|A|≥2)的色唯一性

设G是简单图，用P（G,λ）表示图G的色多项式，若对任意简单图H使P（H，λ）＝P（G，λ），都有H与G同构，则称G是色唯一图，用K（m,n）－A表示从K（m,n）中删去边子集A所得的二部图，令L2^-s(m,n）＝｛K(m,n)-A||A|=s｝，研究一般形式的K（m,n）－A的色唯一性问题，通过引进色正规图类的概念，使用比较两个色等价图的色划分数的方法，得出G∈L2^-s(m,n）的色等价图仍然是属于L2^-s(m,n）的一般形式数值条件，进一步得出G∈L2^-s(m,n)(2≤s≤4)为色唯一图的一般形式数值条件，所得结果完全覆盖并推广了1997年以前该研究方向的相关结果。     

一类完全三部图K(m,n,r)的色唯一性的判定

设G是简单图,用P(G,λ)表示图G的色多项式,若对任意简单图H使P(H,λ)=P(G,λ),都有H与G同构,则称G是色唯一图。令K(m,n,r)表示完全三部图,证明了(1)设m≤n≤r,0≤r-m≤4,若m≥2,则除去K(2,2,6)、K(2,3,6)、K(3,3,7)、K(3,4,7)外,K(m,n,r)是色唯一图。(2)若n≥4,0≤k≤2,则K(n-k,n,n k)是色唯一图。     

一类K4-同胚图的色等价性

给出了K4-同胚图乜(1，2，5，δ，ε，η)这一类图簇中的所有色等价类，从而刻划了K4(1，2，5，δ，ε，η)的结构特征，并且获得了三对色等价非同构的K4-同胚图。     

轮W_(n+1)和W_(m+1)关于K_r-粘合的色等价类和广义树

设m和n是偶数（m,n≥4）,给出了3个色等价类{{W(n+1)W(m=1)},{K3}},{{W(n+2),W(m+1),K3},{K3,K2}},{{W(n+1),W(m+1),K3,K2},{K3,K2,K1}}的基本特征,分析了它们之间的关系．最后给出了广义树的色多项式P（G）＝λ（λ－1）（λ－q3）…（λ－qn）,（1≤qi≤i－1,i＝3,4,…,n）．这些结果在证明上述3个色等价类是完全类时是有用的．     

完全三部图K(n-k,n-v,n)的色唯一性

设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(GH),则称图G是色唯一图.文献[Lau G C,Peng Y H.Chromatic uniqueness ofcertain complete tripartite graphs.Acta Mathematica Sinica,English Series,2011,27(5):919-926]中提出一个猜想(若k≥v≥2,n≥k2/4+v+1,则完全三部图K(n-k,n-v,n)是色唯一的),并证明了若2≤v≤4,k≥v≥2,n≥k2/4+v+1,则K(n-k,n-v,n)是色唯一的.通过比较三角形子图和无弦四边形子图的个数,证明了若v≥4,k≥2v2+4,n≥(k+2)2/8+3,则K(n-k,n-v,n)是色唯一图。     

一些特殊平面图的圆色数

给出了四类无穷族平面图的圆色数：第一族平面图的圆色数介于3和4之间；最后两族平面图的圆色数都是7/2；第二族平面图的圆色数为11/3，这是一族满足圆色数介于7/2和4之间的无穷族平面图，回答了Gao提出的问题．     

一类完全三部图的色等价图

我们已经得到了一些和完全三部图Km,n,r具有相同色多项式的图的必要条件.利用这些性质,得到了图Km,n,n(where 1≤m≤n)的色等价类.特别地,本文也证明了Km,n,n(2≤m≤n)能够由它们的色多项式唯一确定.