图的列表染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:sunny_cui
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
令G是一个有限简单平面图.用V(G)和E(G)分别表示图G的顶点集和边集,简记为V和E.若存在一个映射π:V → {1,2,…,k},满足Vxy∈E,都有π(x)≠π(y),则称π是图G的一个正常k-染色,也称图G是kk-可染的.图G的点色数x(G)是使得G是k-可染的最小正整数k的值.给图G中的每一个点v一个颜色配置L(v).如果存在一种染色π,满足π(v)∈L(v)且染色π是正常的,我们就称这种染色为L-列表染色,也称G是L-可染的.若对于任意列表配置L,只要|L(v)|≥k对所有v∈V(G)都成立,G都是L-可染的,那么我们称G是k-列表可染的,或称G是k-可选的.图G的列表色数是指使得G是kk-可选的最小正整数kk,记为Xl(G).列表染色是由数学大师Vizing及Erdos,Rubin和Taylor分别独立提出来的.1994年,Thomassen证明了每个平面图都是5-可选的.Voigt在1993年找到了一类非4-可选的平面图.在1996年,Mirzakhani成功构造了一个非4-可选的仅有63个顶点的平面图.这是目前所知的点数最少的非4-可选的平面图.随后Gutner在1996年的文章中说明了一个平面图是否是4-可选的是NP-困难的.近年来,平面图的4-可选问题引起了国内外研究者的极大关注.本学位论文主要围绕此问题展开研究.我们将给出平面图为4-可选的一些新的充分条件.论文框架结构及内容如下:在第一章中,我们先给出本文用到的基本概念,再简述相关领域的研究现状和本文的研究结果.在第二章和第三章中,我们主要使用反证法,通过构造极小反例,运用权转移方法,分别证明了以下两个结果:(1)5-圈不同时与3-圈和4-圈相邻的环面图是4-可选的.(2)每个顶点不同时与3-,4-,5-和6-圈相关联的平面图是4-可选的.在第四章中,我们通过刻画最小度为4且直径为2的极大平面图的结构,证明了如下结果:(3)直径为2的平面图是4-可选的.
其他文献
物流是我国国民经济的基础之一,物流的现代化可以有效的改善我国产业结构,提升我国经济运行的质量。近年来随着国际能源供应形式的波动,能源问题逐渐成为制约物流业发展的重
背景:慢性感染、严重的车祸创伤、恶性肿瘤等常常造成的大范围的难以愈合的骨缺损是临床上骨缺损修复的一大难题。自体骨移植、异体骨移植、人工合成材料等修复方式存在供骨
心室辅助装置恒转速的控制方法,会降低血液动脉压的搏动性,并产生了一系列的并发症,造成抽吸和返流现象。而变转速辅助控制能够使心室辅助装置达到最佳辅助状态,适合长期辅助
目的(1)对H型高血压伴血红蛋白增高组、H型高血压血红蛋白正常组、单纯高血压伴血红蛋白增高组、单纯高血压血红蛋白正常组、健康对照组,5组受试者的凝血指标进行检测,观察各
[目的]胃癌是一种在全世界范围内多发的恶性肿瘤。不少胃癌病人在诊断时就已经发生了肿瘤的转移,这严重影响了患者的生活质量,降低了患者的生存时间。至今为止,晚期胃癌患者
海底地下水排泄(submarine groundwater discharge,简称SGD),是指不论水的组成和驱动力如何,在陆架边缘上所有由海底进入到近岸海域的水流。海底地下水排泄是全球水循环的重要组成部分,是陆地向海洋输送水和各种化学物质的重要渠道,对近岸生态环境具有重要影响。同时,陆架边缘海紧靠陆地,极易容易受到人类活动的影响,海洋每年大约能吸收人类向大气排放CO_2的30%50%,使地球维
美国禁酒运动发端于19世纪初,百年之后国会通过禁酒修正案,标志着禁酒运动初步胜利,禁酒浪潮席卷全国。此后,由于禁酒令激化了社会矛盾,1933年第十八条宪法修正案被废除,轰轰
墨江金厂超基性岩体位于扬子板块和印度板块之间滇西南哀牢山断裂带西侧的云南省墨江县内,该岩体侵入于中下志留统并在墨江金镍矿区东侧广泛出露,在大地构造上隶属于“哀牢山超基性岩带西亚带”。金厂超基性岩体主要由蚀变橄榄岩和蚀变方辉橄榄岩组成,广泛发育蛇纹石化,绿泥石化,滑石化,褐铁矿化,石棉化及菱镁矿化等。在空间上,镍矿化发育在超基性岩体与围岩接触带上。本文通过对墨江金厂超基性岩体和镍矿石的岩石学,岩相学
针对在远距离激光微多普勒探测领域中对于高精度探测的迫切需求。本论文通过对光子外差微多普勒探测的探测机理进行创新性研究,提出基于光子外差的微多普勒探测系统,填补了微弱光信号的微多普勒探测技术空白。本文首先对光子外差和微多普勒探测的国内外研究现状进行了分析和归纳。对光子外差探测系统的机理进行了研究,对光子外差探测系统的工作原理、系统构成、响应模型、传输机理以及频谱提取方法进行了概述。针对目标的微多普勒
稀土元素以其用量少,作用大的特点被人们称为当代工业的维生素。氟氧化物作为基质,具备声子能量低,上转换发光效率高,测温范围广的特点。氟氧化物结合了氧化物和氟化物的优势