平面图的非正常染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:honghe2009
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
如果可以将图G的顶点集合划分为两个部分V1和V2使得在G[V1]中最大度至多为d1,在G[V2]中最大度至多为d2,那么称G是(d1,d2)-可染的.我们已经知道对于任意的(d1,d2)∈ {(2,6),(3,5),(4,4)},每个围长至少为5的平面图是(d1,d2)-可染的.目前还没有明确知道是否存在一个正整数d,使得每个围长至少为5的平面图是(1,d)-可染的.2015年,Choi和Raspaud提出问题:每个围长至少为5的平面图是否为(1,7)-可染的?对图G的每一个顶点v ∈ V(G),都给定一个颜色列表L(v),称这个函数L为图G的一个颜色列表配置.(L,d)*-染色指的是在映射π下,对任意v ∈ V(G)均满足π(v)∈L(v),使得在v的邻点中至多有d个顶点的颜色为π(v).如果在图G中对于每个顶点v ∈ V(G),任意列表均满足|L(v)|≥ k,使得G是(L,d)*-可染的,那么我们称G是(k,d)*-可选的.2007年,Xu和Zhang猜想:不包含相邻3-圈的平面图是(3,1)*-可选的.以上提及的问题与猜测,目前均没有得到完整的解答.本学位论文着重围绕这两个问题,运用权转移方法对平面图类展开深入的研究.论文共分为三个章节.在第一章中,我们给出本学位论文所用到的基本概念,简述相关领域的研究现状并呈现了本文的主要结果.在第二章中,我们研究(1,7)-可染的平面图类.证明了:每个围长至少为5且不包含相邻5-圈的平面图是(1,7)-可染的.在第三章中,我们探讨了平面图的(3,1)*-可选性.找到了满足Xu-Zhang猜想的充分条件,即证明了:不含相邻3-圈且不含8-圈的平面图是(3,1)*-可选的.
其他文献
由于风能、太阳能等新能源在存储、运输方面所面临的挑战,新能源的广泛应用需要设计开发出一种功率密度高、能量密度高,循环寿命长的能量存储运输设备。超级电容器由于使用寿
本研究以海藻酸钠为壁材,采用单凝聚法,以氟铃脲为芯材制备微胶囊,对影响氟铃脲微胶囊形貌和包封率的因素进行了研究,优化了微胶囊的制备工艺,通过扫描电镜、粒径分析仪、红
两性霉素B(Amphotericin B,AmB)是一种多烯类抗生素,在1995年从链霉菌的培养液中分离而得来的。AmB是可运用于全身性真菌感染的广谱抗真菌药,它一直是治疗真菌感染的黄金标准
铸钢材料具有良好的力学性能,其强度高、塑性好、韧性好、适用性强,逐渐在建筑结构中得到了广泛应用,其主要形式为铸钢节点,通常用在一些重要场馆的关键受力位置。在一定程度
随着国民经济的高速迅猛发展,矿产资源以极其惊人的速度快速消耗,客观上由于固体非能源矿产资源的不可再生性,矿产资源开发必须走源头上节约与过程中充分利用的发展道路。为
随着互联网技术的迅速发展,各种丰富多彩的新业务也逐步加载到网络上,使得IP网络变得更加臃肿而显露出很多弊端。于是软件自定义网络(SDN),一种新的网络结构被提出,OpenFlow
本文主要研究了两个科学问题,一是对半导体纳米晶的金属异价掺杂问题:采用“由外及里”的离子交换方法,利用膦配体(如三丁基膦等)诱发的阳离子交换合成掺杂有异价离子Cu~+的I
推动构建全覆盖高质量的监督体系天津市纪委书记、监委主任邓修明监督是纪检监察机关基本职责、第一职责,要聚焦系统集成、协同高效,推动构建以党内监督为主导、各类监督贯通
我国侦查讯问录音录像制度的功能定位经历了由偏向固定口供到保障犯罪嫌疑人合法权益、防止刑讯逼供的转换过程,这一过程也对录音录像制度的完整性产生了一定影响。在研究录
Cu及Cu合金材料是一种重要的有色金属材料,由于具有优异的物理和力学性能,它在电子工业等领域获得了广泛的应用。但随着科学技术的快速发展,尤其是微电子工业的快速发展,传统