一类2-连通(n,n+2)-图的色等价与色惟一性

图的色等价与色惟一性是用代数方法研究图论中着色问题一个有着重要意义的研究方法．关于2-连通(n，n 2)有4长圈或两个三角形，或围长为5且不与K4同胚的图族的色等价与色惟一问题已有结果．本文基于图的同胚分类和色多项式系数的比较，给出2-连通(n，n 2)围长为6又不与K4同胚的图族的色等价子族和色惟一子族．     

两类2连通(n,n+4)图的色唯一性

2连通的(n,n 4)图是有n个顶点n 4条边的连通图,利用图的色多项式理论研究了两类2连通的(n,n 4)图的色性,由此部分或完全解决了图G5和图G12的色唯一性问题.     

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

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

一类图的色性

证明色多项式的根全为非负整数的4色图含有K_4子图,并讨论了此类图的色性。     

两类2连通的(n,n+4)图的色性的判定

文献[5]和[6]分别研究了(n,n+2)图和(n,n+3)图的色性,并得到了一些色唯一图.研究了两类2连通的(n,n+4)图,并给出了其色不唯一的证明.     

两类n+3阶n色的色唯一图

用Tn(a,b,c)表示完全图Kn及其外一边uw作一些边后得到图,使|N(u)∩V(Kn)|=a,|N(w)∩V(Kn)|=b,|N(u)∩N(w)∩V(Kn)|=c.Tn(a,b,c)的边uw剖分一个顶点v得到的图为Fn(a,b,c).研究Fn(a,b,c)的色性问题,并给出Fn(a,b,c)是色唯一图的两个充分条件.     

二部图的3分划数及色惟一性的若干新结果

研究了当p≥q≥s 1≥10时,K-s(p,q)中图的3分划数的计算公式和3分划数一些下界及其极图,并得到了许多新的色惟一二部图.     

一类图簇H_i~(SS*(1))(q,n(rm+1))伴随多项式的因式分解

通过研究图簇HiSS*(1)(q,n(rm+1))的伴随多项式的因式分解,证明了这类图簇补图的色等价图的结构定理。     

一类色等价图的图特征

给出了一个有割点的连通图Ｇ是色唯一的充分必要条件为Ｇ由一个色唯一,顶点可迁图连一尾构成,进而证明了若Ｍ为色唯一,不含分离边的连通图,且Ｐ（Ｇ,λ）＝（λ－１）＾ｋｐ（Ｍ）则Ｇ含一子图同构于Ｍ及Ｋ个桥。     

一类图的色唯一性

利用图的色多项式和图的结构间的内在联系,以及图的色数和点的度之间的关系,把满足一定条件的图分成几种情形,证明了当ｎ≥３,ｍ≥３时,由完全图Ｋｎ和图Ｃｍ重叠于一条边得到的一类科是色唯一的。     

完全t部图K（n-k,n,…,n）的色唯一性

设P(G,λ)是图G的色多项式.如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称图G是色唯一图.通过比较图的特征子图的个数,讨论了由文献[Koh K M, Teo K L. The search for chromatically unique graphs. Graphs and Combinatorics, 1999,6: 259-285]中提出的猜想(若n≥k 2,则完全三部图K(n-k,n,n)是色唯一图);推广了文献[Liu Ru-yin, Zhao Hai-xing, Ye Cheng-fu. A complete solution to a conjecture on chromatic unique of complete tripartite graphs. Discrete Mathematics, 2004, 289: 175-179]中的结果(若n≥k 2≥4,则K(n-k,n,n)是色唯一图;若n≥2k≥4,则K(n-k,n-1,n)是色唯一图);证明了若n≥k 2≥4,则K(n-k,n,...,n)是色唯一图,若n≥k 2≥4,则K(n-k,n-1,n,...,n)是色唯一图.     

完全三部图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)是色唯一图。     

一族2─连通（n，n＋2）─图的色类

主要研究了所有具有ｎ个顶．６．，ｎ十２条边，因长是５，且同胚于Ｋ４的２－连通图的色多项式唯一性，得到了三类色唯一的图，对于其中非色唯一的图，给出了它的色类．     

2-连通［4,1］-图的Hamilton圈

如果G的任意s个点的导出子图中至少含有t条边,则称图G为［s, t］-图。本文证明了以下结果：2-连通［4,1］-图是Hamilton图的充要条件是它不同构于三类特殊的图。     

2-连通[4,1]-图的Hamilton圈

如果G的任意s个点的导出子图中至少含有t条边,则称图G为[s,t]-图.本文证明了以下结果:2-连通[4,1]-图是Hamilton图的充要条件是它不同构于三类特殊的图.     

极小3-连通双临界图的点着色数

证明了极小3-连通双临界图的点着色数小于等于4.