几种特殊图的均匀边染色

研究立方Halin图以及一些倍图的均匀边染色,利用换色法、构造法和归纳法得出：立方Halin图和路的倍图都是均匀的,星的倍图都有均匀4-边染色．     

3-正则Halin图的完备染色

研究了3-正则(或立方)Halin图的完备染色,针对非轮图的3-正则Halin图,提出了一种具体的完备染色,简单确定了非轮图(W_n)的3-正则Halin图的完备色数是6,且使得3-正则Halin图的完备染色可用计算机实现。     

Halin图的均匀边染色

图G的一种均匀k-边染色是指用k种颜色去染G的边使得对G的每一个顶点v，任何两种颜色染与。相关联边的数目最多相差1．证明了对任意的大于3的整数k，Halin图都有均匀k-边染色；讨论了k=3的情况．     

Halin 图的均匀边染色

图G的一种均匀k 边染色是指用k种颜色去染G的边使得对G的每一个顶点v ,任何两种颜色染与v相关联边的数目最多相差 1.证明了对任意的大于 3的整数k,Halin图都有均匀k 边染色 ;讨论了k=3的情况     

两类近似Halin图的双约束边染色

证明了两类近似Halin图的双约束边色数均满足χ_e／vf(G)=F_M(G)。     

Halin图的邻点可区别全染色

一个正常的全染色满足相邻顶点的顶点及其关联边所用的色集合不同时,称为邻点可区别全染色,其所用的最少的颜色数称为邻点可区别全色数,本文刻画了Halin图的邻点可区别全色数。     

Halin图的一个点强全染色法

针对Halin图的点强全染色问题,提出一个有效的染色法———逐圈着色法,而且方法给出的方案也是最优的,即用最少的颜色完成Halin图的点强全染色.同时还确定了最大顶点度是3的Halin图的点强全色数的上下界,即上界为6,下界为5.     

Halin图的消圈数及点染色问题

Tutte关于3-连通图的结构定理表明:每一个3-连通图都可由某个轮图(也是Halin图)经顶点分裂逐步得到.这表明了Halin图在图结构研究中的地位和作用.首先研究得到了近正则Halin图的消圈数的上、下界并证明了上述界是紧的,接着得到了最大度为k或最小度为k的Halin图的消圈数所满足的界;此外还研究了Halin图的点染色问题,给出了它的点色数定理的一个新证明.     

伪Halin-图的无循环边着色

图G的无循环边着色是指图G的正常的边着色且任意的圈上不着双色.图G的无循环边色数是指对G进行无循环边着色所需的最少色数k,记为a′(G).给出了伪Halin图的无循环边色数满足猜想a′(G)Δ(G)+2,并且对任意的伪Halin图G且G≠K4,有a′(G)=Δ(G).     

估计n-连通图中非基本边的数目

利用Atom的概念和Halin定理的几个结果,对n-连通图中非基本的数目做了估计,以γ(G)表示图G中非基本边的数目,得到了关于γ(G)的3个定理,其中定理1是Halin定理的推广。     

Halin图的集染色

对于非平凡连通图G,G的k集染色是指映射c：V（G）→Nk,对任意顶点v∈V（G）,定义邻色集cN（v）={c（u）｜u∈N（v）},若对uv∈E（G）有cN（u）≠cN（v）,则称c为G的一个k集染色.满足上述条件的最小k值称为G的集色数,记为χs（G）.为了更快更有效地给Halin图着色,采用集染色的着色方法,证明了当p≥4时,Halin图G（Cp,Tq）的集色数是3,并且还证明了对任意的Halin图G（Cp,Tq）,有p＋1≤q≤2p-2成立.     

关于图的全荫度和列表全荫度的一些结果

图G的全图T(G)是以V(G)∪E(G)为顶点集的一个图,其中两个顶点相邻当且仅当它们在图G中对应的元素是相邻或关联的.图G的全荫度ρ"(G)是将其全图的顶点集V(T(G))划分为最少的子集数,使得每个子集在全图中的导出子图是一个森林.列表全荫度硝(G)是全荫度概念的列表染色的版本.本文证明了:(1)对完全图‰,ρ"(Kn)=「(n+1)/2];(2)对完全二部图Kn,n,ρ"(Kn,n)=「(n+2)/2];(3)对Halin图G,ρl"(G)≤「(△(G)+2)/2].     

非连通图G+e∪H_(k-1)的优美性

证明了当k≥2时,非连通图G+e∪Hk-1是优美图,其中G是特征为k的平衡二分图,Hk-1是任意一个k-1条边的优美图.     

Halin图和Series—Parallel图的星荫度

证明了：（１）所有Ｈａｌｉｎ图的星荫度为３，和（２）所有Ｓｅｒｉｅｓ－Ｐａｒａｌｌｅｌ图的星荫度小于等于３。     

再探非连通图C_(4m-1)∪G的优美标号

讨论了非连通图C4 m-1∪G的优美性,给出了非连通图C4 m-1∪G是优美图的2个充分条件.     

非连通图C_(4m-1)∪G的优美标号

讨论了非连通图C4 m-1∪G的优美性,给出了非连通图C4 m-1∪G是优美图的2个充分条件.     

Halin图的圈着色

对3连通图Halin 图,确定了其圈色数,并得到较好结果     

立方Halin图的完备色数

 证明了每个立方Halin图H是完备6可着色的,并且H有一个完备6-着色,使得每一种色出现在每一个面(顶点)以及与其相邻(关联)的顶点、边和面的着色集中。