Halin-图的列表染色

Halin-图是3-连通平面图,且存在一个面,删除关联于该面的边后是一棵树,图的列表染色是任给图G的每个顶点V配一颜色集合L(V),满足|L(V)|=k,k为某确定正数;G的每个点若均可着从L(V)中选出的一种颜色,使得任意两个相邻近的点着不同的色,则称G是k-可选择的,Min(k)称为G的选择数或列表色数,记x_L(G),本文证明了Halin图的列表色数为3或4,并得到了x_L(G)=3的充要条件。     

Halin图的边列表染色

图的染色是图论的重要研究内容之一．平面图染色是其中的一个主要方面．有各种各样的染色方式，近来，又出现了列表染色［１］．定义１称图Ｇ是ｋ－边可选择的．如果任给ｅ∈Ｅ（Ｇ），和边ｅ的任给颜色集Ｌ（ｅ），｜Ｌ（ｅ）｜＝ｔ，都可以选一种颜色σ（ｅ）∈Ｌ（ｅ）...     

Halin图的一些路分解

本文证明了：若Ｇ是Ｈａｌｉｎ图,则Ｇ的线性荫度为［△（Ｇ）／２］,点荫度和线性点荫度为２,路分解数等于它的奇数度顶点的一半。     

关于图的全染色和列表全染色方面的一些结果

证明了如下结果：一个简单连通图G的全色数和列表全色数都为△＋1，如果它存在一个支撑子树T使得△（G）≥6和△（G\E（T））≤2，或者△（G）≥4和△（G\E（T））≤1。     

关于图的全荫度和列表全荫度的一些结果（英文）

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

轮图的列表染色

文章给出了边列表染色和顶点列表染色的定义,证明了对轮图,边选择数x (G)=△(G),点选择数xLV(G)=4,点边选择数xLVE(G)=△(G)+1.     

系列-平行图的列表染色

系列 -平行图是没有子图与K4同胚的图 .设G为一个系列 -平行图 .如果对任意的边e∈E(G) ,有 f(e) ≥max{ 4,Δ(G) } 则G是f 可列表染色的 .同时还确定了所有系列 -平行图的边色数 .     

Halin图和Series—Parallel图的星荫度

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

系列—平行图的列表染色

系列－平行图是没有子力与Ｋ４同胚的图。设Ｇ为一个系列－平行图。如果对任意的边ｅ∈Ｅ（Ｇ），有ｆ（ｅ）≥ｍａｘ（４，Δ（Ｇ）），则Ｇ是ｆ－可列表染色的同时还确定了所有系列－平行图的边色数。     

图的列表着色

本文围绕列表着色展开讨论,将列表着色方面的已有结论进行了整理和简要的证明及补充说明.本文对一些猜想的特殊情况进行了论证.     

关于邻点可区别全染色的几个新结果

邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同.顶点ν的色集是ν的颜色及其与ν关联的所有边的颜色.我们给出了几类特殊图的邻点可区别全色数.     

平面图的完备List染色

设Ｇ是２－连简单平面图，ｘ＾ｖｅｒ（Ｇ）为Ｇ的完备Ｌｉｓｔ和选择数。本文证明若Ｇ为最大度△（Ｇ）≥７的２－连通外平面图，则ｘ１＾ｖｅｒ（Ｇ）＝△（Ｇ）＋１     

外平面图的边面 List 染色

设Ｇ是无割点平面图，ｘｅｆｌ（Ｇ）为Ｇ的边面Ｌｉｓｔ选择数。本文证明了若Ｇ为最大度Δ（Ｇ）≥６的无割点外平面图，则ｘｅｆｌ（Ｇ）＝Δ（Ｇ）。     

关于图全着色的几个结果

引入了一种研究图全着色问题的新方法，即从考虑图中的圈出发研究全着色问题．运用该方法确定了一些图的全色数，并给出了图全色数的一个上界．     

荫度与全独立数全覆盖数的关系

研究了图的荫度、边荫度与其余独立数、全覆盖数间的关系，得到了不可改进的结果。     

特殊平面图的线性二荫度

线性k-森林是指一个图G,它的每个连通分支是长至多为k的路．图G的线性k-荫度是指使得G可以边划分成m个线性k-森林的最小整数m,用lak（G）表示．本文探讨特殊平面图的线性二荫度,得到的结论有：1）每个3-圈不重边的平面图G,有la2（G）≤[△（G）／2]＋10;2）每个3-圈不重点的平面图G,有la2（G）≤[△（G）／2]＋7;3）每点至多关联[△（G）／2]个3-面的平面图G,有la2（G）≤[△（G）／2]＋10．     

关于图的边染色方面的一些结果

改进了一些边染色临界图的边数的下界．同时证明了：对没有４圈或任何两个３面都不同时关联于一个点的平面图,关于边染色的平面图猜想成立．     

特殊平面图的全染色

给定一个图G,G的全k染色是指至多用k种颜色,对G的顶点和边同时进行染色,使得相邻的或相关联的两个元素(点和边)不染同一种颜色.图G的全染色数xT(G)是指使G全k染色的最小整数k.Δ(G)是G的最大度,本文对不含从4到k的圈,且3-圈不重点的平面图得出的结论有:如果(Δ,k)分别是(6,4),(5,5),(4,11),则G的全染色数是Δ 1.     

关于图的哈密尔顿性的一些新的结果

关于哈密尔顿图和哈密尔顿连通的两个基本结果是Ore给出的:设G是一个n(n≥3)阶图,如果对于G的任意一对不相邻顶点u,v,有d(u) d(v)≥n或n 1,则G是哈密尔顿图或哈密尔顿连通的.设G是一个图,对于任意u∈V(G),令N(u)表示u的邻点集;对于任意U∈V(G),令N(U)=∪u∈UN(u).本文利用插点方法,给出了关于k或(k 1)-连通图(k≥2)G是哈密尔顿的,哈密尔顿连通的或1-哈密尔顿的统一证明.其充分条件是关于|N(S)| |N(T)|与n(S ∪T)的不等式,这里S,T是图G的任意两个不交的独立集,并且|S|=s,|T|=1,S∪T也是一个独立集,这里n(S∪T)=|{v∈V(G):dist(v,S∪T)≤2}|.     

关于临界图的若干结果

Ｖｉｚｉｎｇ’ｓ猜想：ｎ阶Δ－临界图的边数ｍ满足ｍ≥（ｎΔ－ｎ＋３）／２。本文证明了当ｎΔ＝３时猜想也成立以及当５≤Δ〈ｎ／２，ｎΔ＝４时猜想也成立。同时给出了临界图的两个新的性质。