SP(i)类图簇的伴随多项式的因式分解及其色性分析

通过研究图的伴随多项式的因式分解,给出了证明色等价图的结构性质和非色唯一图的新方法.     

稠密图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的色多项式和伴随多项式.     

一类图色等价的充分必要条件(英文)

给出了两个伴随最小实根不小于-4的图伴随等价的一个充分必要条件.据此,也给出了这些图的补图色等价的一个充分必要条件.     

图GS*i(P,2∑nj=1mj)的伴随多项式因式分解的图论方法及应用

通过研究图的伴随多项式的因式分解,给出了证明非色唯一图的一种新方法,并且得到了若干图簇的色等价图的结构性质.     

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

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

Γφ*G(i,j)r(2k+p)+1型图簇的伴随多项式的因式分解及色性

通过研究Γφ*G(i,j)r(2k p) 1类图簇的伴随多项式的因式分解,证明了这类图簇的补图的色等价图的结构性质和非色唯一性.     

一类图簇S_(k(rm+1)+1)~(S*(1))的伴随多项式因式分解

通过研究图S^S^＊（1）k（rm＋1）＋1的伴随多项式的因式分解,证明这类图簇的补图的色等价图的结构定理。     

二部图 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年以前该研究方向的相关结果。     

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是色唯一图等结论.     

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

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

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

设Ｐ（Ｇ,λ）表示简单图Ｇ的色多项式;若对任意简单图Ｈ 满足Ｐ（Ｈ,λ） ＝ Ｐ（Ｇ,λ）,都有Ｈ 与Ｇ同构,则称Ｇ是色唯一图;设Ｋ（ｍ ,ｎ,ｒ） 表示完全三部图;本文证明了：（１） 若ｎ ＞ ｋ ＋ ｋ２／３,则图Ｋ（ｎ － ｋ,ｎ,ｎ） 是色唯一的,（２） 若ｎ ≥８,则Ｋ（ｎ － ４,ｎ,ｎ） 是色唯一的;     

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

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

一类5—桥图的色唯一性

设P(G;λ）是图G关于变量λ的色多项式。如果对任意图H,P（H;λ）＝P（G;λ）,都有H和G同构,则称图G是色唯一的,由连接两个顶点的s条内部不交的路组成的图叫s-桥图,本文给出了一类5-桥图F（2,2,2,a,b)(a≥b≥3)是色唯一的充分必要条件,推广了关于5－ 图色唯一性的已有结论。λ     

一类图的色唯一性

让W_(n,n-2)表示删去轮形图W_n中一条轮辐所得到的图.W(n,n-2,k)表示在W_(n,n-2)中由k个点u_1,u_2,…,u_t组成的独立集取代W_(n,n-2)中的2度点u,使得u_j(j=1,2,…,k)仅与u所相邻的两个点x,y相邻接而得到的。本文证明了当k=2,n≥4为偶数时,这类图是色唯一的。     

5—桥图的色唯一性

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

一类色唯一的K_1-同胚图

令K4(i,j,k,l,m,n)表示图G的色多项式,如果P(G)=P(H),称G和H色等价;如果对任意图H,当P(H=P(G))时,都有H和G同构,称G是色唯一的.令K4(i,j,k,l,m,n)表示两两三度点间的路长分别为i,j,k,l,m,n的K4-同胚图.作者对集合{i,j,k,l,m,n}由3个不同值组成,且等于每个值的路都恰有2条的K4-同胚图的着色进行了研究,得到了1类色唯一的K4-同胚图.     

非色唯一的连通顶点可迁图的广泛存在性

本文中,我们构造性地证明了:对应于每一个给定的色唯一的连通顶点可迁图,均存在着无穷多个与之对应的非色唯一的连通顶点可迁图.据此,我们部分地回答了G.L.Chia在[4]中提出的第二个问题.     

一些圈加边图的着色

设P(G;λ)表示图G的色多项式,若P(H;λ)=P(G;λ),称H和G色等价.设ξ是图组成的集合,若对任意图H,当H和ξ中的某一图色等价时,都有H ∈ξ,称ξ是完全色等价类.本文给出了由部分广义多边形树Gsl(a,b;c,d)(s+t=2)组成的一个完全色等价类.     

完全四部图的色性

设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)是色唯一的．