几类非色唯一的连通顶点可迁图

给出了几类非色唯一的连通顶点可迁图,即kKq kKq(k≥2,q≥2)、kCn kCn(k≥2,n≥3)和kRn kRn(k≥2,n∈{3,4,6,12}),其中Kq是具有q个顶点的完全图,Cn是具有n个顶点的回路,Rn是具有n个顶点的最大正则平面图,是两个不相交图的Zykov乘积运算。     

关于色唯一图的注记

设P(G;λ)是图G的色多项式,如果对任意图H,当P(H;λ)=P(G;λ)时,都有H和G同构,则称图G是色唯一的。本文给出了由两个块H和K2构成的图G是色唯一的当且仅当H是色唯一点可迁的。     

一类图的色唯一及色等价

本通过比较一类图的色多项式，得到了大量的色唯一图，同时也讨论了色不唯一图。     

不连通非标定图的色多项式

本文研究不连通的非标定图的色多项式的基本性质,给出了这类非标定图的色多项式的一般计算公式.     

连通非标定图的色多项式

本文研究连通的非标定图色多项式的基本性质，给出了若干类常见连通非标定图色多项式的一般表达式。     

一族2—连通（n,n＋2）—图的色类

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

几类图色等价的充分必要条件

在微积分罗尔定理理论基础上,运用归纳法证明了两个多项式恒等的一个充分条件,进而利用色数、围长、补图的理想子图数给出了两类图n+s(s,n∈Z+)阶n-色图色等价的充分必要条件,这为构造色等价图提供了新方法,由此得到几类新的色等价的n+3阶n-色图.     

一类稠密图色唯一的充要条件

设n≥1,T(1,1,n,4,1)表示从Pn+1的两个端点分别引出两条长为1,1和4,1的路所得到的图.在图G伴随唯一当且仅当-G色唯一的基础上,利用图的特征标、伴随多项式的代数性质及最小实数根的规律,证明了一类稠密图T(1,1,n,4,1)色唯一的充要条件是n≠1,4,7.     

k色图的连通性

研究和讨论了图的顶点着色问题中k色图的连通性,利用归纳与迭代的方法证明了对于任何k色连通图G,存在顶点V(G)的一个着色X1,X2,…,Xk,使得对该着色类中任意顶点集Xi所诱导出的Gk的子图Gk(Xi)都是连通的.从而证明了Chen,Schelp和Shreve关于k色图的连通性的一个推测.最后将所得的结论作了进一步推广.     

一类稠密图色性的刻画

针对大量非色唯一图,利用图的伴随多项式,最小根及其特征标的性质研究了一类稠密图的色性:完整刻画了该类稠密图的色等价图类,并给出了其色唯一的充要条件.这为图的色性研究提供了新的工具和方法.     

一类色惟一的图

本文通过研究图的色多项式,及色多项式中系数来证明由ｎ 个顶点,ｎ ＋ ２ 条边（ｎ ≥７） 组成的一类图Ｚｎ 是色惟一的。这类图是从轮图中删去若干条幅而得到的。     

有关某类图色惟一性的注

本文给出文 [1 ]定理 1 8中论证的两类色惟一图H5(j,k ,l)及H6(p ,q)的反例。这两类色惟一图最早出现在文 [2 ]和 [3]中。     

关于两类图的圈唯一性

设 C(G;)是图 G 的圈多项式,如果对任何图 H,C(G;)=C(H;导出 G 同构于 H,则称 G 为圈唯一的。在本文证明了下面的两类图 i)T_(p,r,t ii)P_(p-1)+K_1是圈唯一的。     

图D_n_1∪D_n_2∪…∪D_n_1∪P_（q－1）的补图的色唯一性

本文利用伴随多项式的性质，证明了形如Ｄ＿ｎ＿１∪Ｄ＿ｎ＿２∪…∪Ｄ＿ｎ＿１∪Ｐ＿（ｑ－１）的一类图在一定的条件下是伴随唯一的，从而证明了这类图的补图是色唯一的。     

有关非标定图色多项式的组合含义

本文根据Ｐ．Ｈａｎｌｏｎ给出的计算非标定图色多项式的表达式,地标定图的自同构群中各种转换情况的讨论,给出非标定图色多项式的前四项色系数的组合表达式,并归纳了表达式中各参数计算的一般步骤。本文还给出坟解非标定图色多项式的实例,以验证理论推导所得的结论。     

几类积图的强边着色

图G的强边着色是指一个正常的边着色,同时对任意长为3的路上的边不能有相同的颜色.图G的强边色数是指在G的所有强边着色中所用色数的最小者.研究了几类积图的强边着色,并给出了相应图的精确的强边色数值.     

一类循环图的计数

讨论了4度循环图的结构。所有n阶4度非同构的连通循环图被分为两类:Ⅰ类和Ⅱ类。给出了计算Ⅰ类循环图的计算公式,改进了关于n阶4度非同构的循环图的计数公式。     

一些图的K-优美性

本文证明了在齿轮图W_n的每个齿凹处分别加任意的m_1,m_2,…,m.条边,只要满足条件max{m_1,m_2,…,m_n}≥n-2,则所得图为K-优美,并且给出了一些单圈图的K-优美结论,其中K为任意非负整数.     

指标图的一些结论

给出求指标标号的IE算法，并证明了树T是指标图。文献[1]猜想唯一圈图J（Cn）指标图，本文证明了这个猜想在n＝3时是正确的，同时也证明了圈Cn的一点接任意一棵树所得图是指标图。