边色临界图的1-因子和几乎1-因子的存在性

根据Vizing邻接引理和关于临界图的独立数的一个结论,利用图的1-因子和几乎1-因子存在的充要条件,采用结构图论的方法证明了：1）若G是2n阶△～临界图,且△≥n,δ≥n-2,则G存在1-因子;2）若G是2n＋1阶△-临界图,且△≥n＋1,δ≥n-2,则G存在几乎卜因子．     

均衡二分图中哈密顿[k,k+1]-因子的存在条件

设k≥2是一个正整数,若G是顶点数n≥8k-12的均衡二分图且是(n/4 1)-临界的,则对G的任一给定的哈密顿圈C,G都有一个[k,k 1]-因子包含C.该结论改进了现有的一些有关哈密顿[k,k 1]-因子存在性的结果.     

图的2-正交[0,kj]m1-因子分解

在[0，k1 … km-m 1]-图的正交[0，kj]1^m-因子分解问题的基础上，讨论了[0，k1 … km-m 1]-图的2-正交[0，kj]1^m-因子分解问题，并给出了该问题的一个充分条件。     

广义θ-图的邻强边染色

u,v两点间至少连4条内部不相交的路且至多有一条长度为1的路,称为广义θ-图.本文得到了广义θ-图的邻强边色数.     

关于(a,b,s)-临界图的邻域条件

设G是一个n阶的图.设a,b和s是整数,使得b＞a≥1.设δ(G)是G的最小度.证明了:如果δ(G)≥(k-1)a+s,n≥(a+b)(k(a+b)-2)/b,并且|Nc(x1)∪NG(x2)∪…∪NG(xk)|≥an/(a+b)+s对V(G)任意的独立子集{x1,x2,…,xk}都成立,这里k≥2,则G是一个(a,b,s)-临界图.这个结果在某种意义上是最好的.     

若干色临界图和色极小图的构造

一个图Ｇ,若对任意的顶点Ｖ（边ｅ）,Ｘ（Ｇ－ｖ）＜Ｘ（Ｇ）（Ｘ（Ｇ－ｅ）＜Ｘ（Ｇ））,则称Ｇ是色临界的（色极小的）．给出了色临界图和色极小图的几个构造方法,并探讨了这些构造方法的性质。     

广义θ-图的邻强边染色

u,v两点间至少连4条内部不相交的路且至多有一条长度为1的路，称为广义θ-图．本文得到了广义θ-图的邻强边色数．     

连通图的1-因子和(g,f)-覆盖图

设G是一个连通图且有一个1-因子F,g和f是定义在V(G)上的整数值函数并且对每个x∈V(G)都有0≤g(x)＜f(x)≤dG(x).若对每个xy∈F有f(x)=f(y)且G-{x,y}是(g,f)-覆盖图,则G是(g,f)-覆盖的.     

几乎正则的n—部竞赛图的若干性质

设D是一个有向图,D中所有可能的两点x与y(x与y可以相同）的出度与入度之差的绝对值的最大值叫做有向图D的非正则,工记为i(D),如果i(D)=0,则称D为正则图;如果i(D)=1,则称D为几乎正则图,本文给出了几乎正则的n－部竞赛图的若干性质。     

两类齿轮图的分数色数

分数着色是在正常着色的基础上提出的,拓展了图着色的研究领域,便于更好的研究图的结构.主要研究了齿轮星图,齿轮风车图的分数色数,分数关联色数和分数全色数,给出了计算这些图形分数色数的公式,并且对公式进行了证明.     

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

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

图的全谐调着色数

图的全谐调着色数表示为Th(G)是相邻的点与边着不同颜色 ,且任何两个不同的边上有不同的三元颜色组的最小着色数。本文给出了关于图的全谐调着色数的各种定理     

图的范畴积的圆色数

图的圆色数的定义是图的色数的一个自然的推广,它是由Vince首先提出的.本文主要研究图的范畴积的圆色数.     

图的星色数的两个结果

图G的星染色是图G的正常点染色,使得图G中没有长为3的路2-染色.通过应用概率方法中的非对称局部引理,证明了任一最大度为Δ的图的星色数χs（G）≤48Δ3.通过应用第一矩量原理和Markov不等式,证明了对任一有n个顶点的最大度为Δ的图G,其星色数χs（G）≤nΔ.     

Halin图的色数问题

Halin图G=T∪C,其中T为每一非悬挂点(内点)度数至少为3的平面树,C为连接T的所有悬挂点的圈.文章分别讨论了Halin图的星色数、面色数及分数色数.     

几类积图的强边着色

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

On the ｛P2,P3｝-Factor of Cubic Graphs

Ler G = （ V, E） be a finite simple graph and Pn denote the path of order n. A spanning subgraph F is called a { P2, P3 }-factor of G if each component of F is isomorphic to P2 or P3. With the path-covering method, it is proved that any connected cubic graph with at least 5 vertices has a { P2, P3 }-factor F such that｜P3（F）｜P2（F）｜, where P2（F） and P3（F） denote the set of components of P2 and P3 in F, respectively.     

直径为2的图的P_2路色问题

针对以r为参数的直径为 2的图的 (2 ,r)路色数的计算复杂性问题 ,从直径为 2的图及任意给定的整数r ≥ 3,图的 (2 ,r) 路色数问题是NP 完全的入手 ,给出直径为 2的 (2 ,2 )的路色图的一个好的刻划 ,并由此给出该问题一个多项式时间算法 ,从而解决了以r为参数的直径为 2的图的 (2 ,r)路色数问题的计算复杂性分类