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=（V,E）,对于V中任何一个点集S,若G-S是一个无圈图,则称S是图G的一个消圈集,且称min{|S||S是图G的消圈集}为图G的消圈数,记为Φ（G）.本文考虑联图的消圈问题,得到了几类联图消圈数的精确值.设G_m和G_n分别表示阶数为m和n的简单连通图,则联图G_m∨G_n的消圈数满足:min{m,n}≤Φ（G_m∨G_n）≤min{m+Φ（G_n）,n+Φ（G_m）}.本文中几类联图的消圈数证实了上述不等式的上界是紧的.特别地,当G_m和G_n都为树时,可由不等式直接得到Φ（G_m∨G_n）的精确值.     

△(G)≥6的Halin图的点强全染色

图G(V，E)的正常k-全染色σ称为G(V，E)的k-点强全染色当且仅当A↓v∈V(G)，N[v]的元素染不同色，其中N[v]={uluv∈EG)}∪{v}，xT^vs(G)=min{k|存在G的k-点强全染色}称为G(V，E)的点强全色数。本文证明了：对于△(G)≥6的Halin图G(V，E)，有xT^vs(G)≤△(G) 2，其△(G)表示图G的最大度。     

Halin图的圈基结构

本文用代数的思想研究了Halin图的圈基结构,并证明了Halin图的最小圈基所具备的一系列性质。     

Halin图的圈着色

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

3-正则Halin图的完备染色

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

关于路Pn和圈Cn的幂图的消圈数

讨论关于路Pn和圈Cn的幂图的消圈数.对于任意给定的次幂m,文中得出了路Pn和圈Cn的幂图的消圈数的准确值.另外,还给出了路Pn和圈Cn的幂图的最大导出树.     

Halin图的无圈边着色

设f是图G的一个正常边着色,若在f下G中没有2-色圈,则称f是图G的一个无圈边着色,其所用最小色数为G的无圈边色数。N．Alon猜想对所有简单图,无圈边色数不超过其最大度加2。本文证明了该猜想对Halin图成立,且当Δ≤4时,其色数不超过5;当Δ≥5时,其色数等于最大度。     

Halin图的一个点强全染色法

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

连通图中圈数

用|V（G）|、|E（G）|和f（G）分别表示图G的顶点数、边数和圈数．设F（k）＝｛f（G）;G是满足|E（G）|－|V（G）|＝k的无环连通图｝,n（k）＝minF（k）和N（k）＝maxF（k）．证明了下述结果：（1）n（k）＝k＋1;（2）N（k）≤2k+1;（3）对每个整数k≥1,N（k）≥2k＋k（k－1）＋1且当1≤k≤4时等式成立;（4）对每个整数k≥1是奇数时,N（k）≥2k3;当k≥2是偶数时,     

Halin图的邻点可区别全染色

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

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

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

Halin图的有点面约束的边染色

研究了Halin 图的有点面约束的边染色,给出了Halin 图的有点面约束的边染色色数的一个精确结果.     

一类外平面图的有界染色

图G的k-有界染色是图G的一个最多有k个顶点染同一种颜色的顶点染色．图G的k-有界染色数χk(G)是指对图G进行k-有界染色所用的最少颜色数．讨论一类外平面图的k-有界染色，给出能在多项式时间内确定其k-有界染色数的一些充分条件．     

图的对策着色和对策色数

图的对策色数Ⅱ Xg(G)是由图的点色数Xg(G)拓展得到的。本文给出了一些图的对策色数,并讨论了图的对策色数的性质。     

图的点强全染色

图G(V,E)的正常k—全染色f叫做G(V,E)的k—点强全染色,当且仅当对任意的w∈V(G),N[w]中元素染不同颜色,其中N[w]={x|wx∈E(G)}∪{w}.并称XvTs(G)=min{k|存在G的k—点强全染色}为图G(V,E)的点强全色数.本文研究了K4-minor free图和外平面图的点强全色数.     

Halin图的1-色数

Ｈａｌｉｎ图的１－色数为２的充要条件和１－色数为３的若干充分条件