特殊1-平面图的列表全染色

来源 :山东大学 | 被引量 : 0次 | 上传用户:jj13148
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文所研究的图为简单的、有限的、无向的、非空连通图。一个图称为是1-平面图如果它可以画在平面上且使得每条边至多交叉另外一条边。对于1-平面图,本文假设G已经嵌入到平面上且满足:  (a)每条边至多交叉一次;  (b)交叉点的数目最小。  图的列表染色是一种特殊的染色方式。设映射L给每个元素α∈V∪E分配一个颜色集合L(α),则称L是图G的一个全列表分配。如果存在一个正常全染色c,使得对每一个元素α∈V∪E都有c(α)∈L(α),则称G是L-全可选的,或L-列表全可染的。如果对任意满足|L(x)|≥k的列表分配L,其中x∈V∪E,都有G是L-全可选的,则称G是k-全可选的,或k-列表全可染的。我们用x"l(G)表示G的列表全色数,指的是使得G是k-全可选的最小整数k。  本文根据1-平面图G及其关联平面图G(x)的结构性质,利用权转移的方法证明特殊的1-平面图,即无交叉3-圈的1-平面图和无交叉3,4-圈的1-平面图的列表全染色问题。文章主要内容如下:  第一章介绍了文章的基本定义和研究背景;  第二章证明定理1:对于无交叉3-圈的1-平面图G,当△≥16时,是(△+1)-列表全可染的,即x"l(G)=△+1。  第三章证明定理2:对于无交叉3,4-圈的1-平面图G,当△≥14时,是(△+1)-列表全可染的,即当1-平面图G的每个点至多关联一个3-圈或4-圈且△≥14时,x"l(G)=△+1.
其他文献
蚂蚁族群最佳化(Ant Colony Optimization)为一崭新的近似求解演算法,由Dorigo;Maniezzo等学者于90年代初期所提出,对于解决一些困难的组合问题,已被证明有相当好的成效。蚂蚁族
欧盟 1 0个新成员国都是较穷的国家 ,目前的人均国内生产总值仅有 1 .0 7万欧元 ,是欧盟老成员国平均值的4 6 %。新成员国当中 ,拉脱维亚的人均国内生产总值最低 ,仅有欧盟 1
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
本文论述了TAF代数的表示。  设A=(A,)是TAF代数(三角逼近有限维的代数),ρ:A→AlgN是Hilbert空间H上的套表示,其中N=Latp(A)是一个套。主要结果为: 1.下列条件等价: (i)kerρ是完全
1949年3月18日,军港葫芦岛沉浸在金黄色的晚霞中。忽然传来了飞机嗡嗡的轰隆声,顷刻间,甲板上有人叫喊:“飞机!”随着他指的方向看去,一架敌双引擎运输机正沿着海岸飞来。来
本论文主要研究了几类Toroidal李(超)代数及Virasoro李(超)代数的结构、表示及其相关的问题. T0roidal李代数首先是由R.V.Moody,s.Eswara Rao,T.Yokonuma二十世纪九十年代提出并
发展方程是包含时间变数t的许多重要的数学物理偏微分方程的统称。本文对一类半线性热传导方程柯西问题整体解的存在唯一性进行了研究。文章讨论了Rn中一类半线性热传导方程
采用扫描电镜和气质联用技术研究纽荷尔脐橙(Citrus sinensis Osbeck‘Newhall’)、南丰蜜橘杨小2-6株系(C.reticulata Blanco‘Yangxiao 2-6’)、红心蜜柚(C.grandis Osbeck
在江苏省阜宁县人民检察院,有一位朴实、随和、忠厚的检察官,他叫孙体春。他多次被各级评为“先进工作者”、“优秀共产党员”,2001年还被江苏省检察院授予“人民满意的检察
请下载后查看,本文暂不支持在线获取查看简介。从历史走向光辉的未来——中共陕西省委党校70年发展掠影 Please download to view, this article does not support online ac