平面图的点染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:mhy8348
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图G的一个正常顶点染色是指k种颜色1,2,…,k对于G的各顶点的一个分配,使得任意两个相邻的顶点分配以不同颜色。若图G有一个正常k-点染色,那么就称图G是k-点可染色的。图G的色数是指G有一个正常后顶点染色的数k的最小值,用χ(G)表示。 图G的一个顶点色列表L是一个颜色集合簇,它指定G的每个顶点υ一个颜色集合L(υ).若G有一个正常的顶点染色π,使得对每一个顶点υ∈ V,有π(υ) ∈L(υ),则称G为L-顶点可染的或者称π是G的一个L-染色。若对每一个满足|L(υ)|≥k,υ∈ V的L,G都是L-点可染的,则称G是k-点可选择的,简称G是k-可选择的。G的顶点列表色数是使得G是k-可选择的最小的非负整数后。 假若染色π是图G的正常顶点染色,并且对于G中的任何一个圈子图C都应用至少3种颜色,那么我们称染色π是G的一个无圈染色。图G的无圈色数χa(G)就是使得G是无圈k-可染的最小的非负整数k。若G有一个正常的无圈染色π,使得对每一个顶点υ∈ V,都有π(υ)∈ L (υ),则称G是无圈L-可染的或者称π是G的一个无圈L-染色。若对满足|L(υ)|≥k,υ∈ V的色列表L,G都是无圈L-可染的,那么称G是无圈k-可选择的。G的无圈列表色数χ<,a>(G)是使得G是无圈k-可选择的最小的非负整数k。 1976年,对于平面图的正常顶点着色,Steinberg提出猜想:每个不包含4-圈和5-圈的平面图是3-可染色的。 2002年,Borodin等人首次研究了平面图的无圈L-染色问题,并且在文献[2]中证明了每个平面图都是无圈7-可选择的。与此同时,他们还在此文献中提出了一个更具有挑战性的猜想:每个平面图都是无圈5-可选择的。 本学位论文主要围绕这两个猜想,对一些平面图类展开研究。 在第一章中,给出本文所用到的基本概念,简述了相关领域的研究现状以及呈现了本文的主要结果。 在第二章中,证明了以下两个结果: (1).每个不包含{4,6,7,9}-圈的平面图是3-可染色的; (2).每个不包含{4,6,8}-圈的平面图是3-可染色的。 在第三章中,获得了以下两个结果: (1).每个不包含4-圈的平面图是无圈6-可选择的; (2).每个不包含4-圈并且任意两个三角形之间的距离至少是3的平面图是无圈5-可选择的。
其他文献
本文研究了几类拟解析系统的中心,等时中心与极限环分支,全文由四章组成。 在第一章,我们对多项式微分系统的等时中心与极限环分支的历史背景与现状进行了概述。 在第二章
国民体质状况和健康水平是一个国家综合国力的重要组成部分,推行体质监测制度是全民健身计划纲要中的重要内容,为保障监测工作规范化和科学性,国家体育总局制定和颁布了《国
本文共包含以下五章内容。第一章简单介绍了本文的研究背景以及主要的研究内容。第二章介绍B样条曲线的定义、性质。第三、四、五章分别介绍了王文涛等提出的带形状参数的均
断裂现象始终是同材料与结构中的孔洞、缺口或裂纹相关联的,在材料的这种宏观不连续部分最明显的特点是应力分布极不均匀,这种现象叫做应力集中。缺陷(孔洞、裂纹、位错等)和应
在声学、电磁学、地震学及其他许多应用领域的大规模的波传播问题的研究中,通常需要在一个长度比波长还要大许多的区域中求波场的分布,在激光的传输和光晶仪器的设计等问题研究
学位
设G为无向图,V(G)为顶点集,E(G)为边集。图G的定向图是把图G的每条边(χ,γ)用弧χγ或γχ代替,得到的有向图(即定向图D无二圈和环)。在给无向图定向的过程中,可使定向图满足各种
偏微分方程在数学、物理、生物等许多个学科领域中有着广泛的应用.尤其是偏微分方程的精确可控性受到了很多国内外学者的广泛关注。对于偏微分方程精确能控性的研究,无论在理
自从1998年以来,复杂网络就成为国内外各界学者研究的一个热点,其中复杂动态网络可以用来描述从生物到技术乃至社会各类开放复杂系统的构架。而博弈论是20世纪初就发展起来的