平面图的3染色和3可选择性

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:gang098
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图G的一个正常k顶点染色是指一个映射φ:V→{1,…,k},使得对任意uv∈E(G),满足φ(u)≠φ(v).若图G有一个正常k点染色,那么就称图G是k点可染色的. 图G的一个顶点色列表L是一个颜色集合簇,它指定G的每个顶点u一个颜色集合L(u).若G有一个正常的顶点染色φ,使得对每一个顶点u∈V(G),有φ(u)∈L(u),则称G为L顶点可染的,或者称φ是G的一个L染色.若对每一个满足|L(u)|≥k,u∈V(G)的L,G都是L点可染的,则称G是k(点)可选择的. 1979年,P.Erdos等人刻画了2可选择图并提出猜想:每一个平面图都是5可选择的,且存在着非4可选择的平面图.1993年,Voigt成功地构造出了非4可选择的平面图.随后,Thomassen证明了每一个平面图都是5可选择的.由此,自然产生这样一个问题:哪些平面图是4可选择的,哪些平面图是3可选择的?1996年,Gutner证明了这个问题是NP困难的.因此,寻找平面图是3或4可选择的充分条件成为图的染色理论中的一个重要研究课题。 1976年,Steinberg猜想:不含4圈和5圈的平面图是3可染色的.Erdos建议去研究下述问题:是否存在一个整数七,使得没有4至尼圈的平面图是3可染色的.到目前为止,Erdos问题的最佳结论为:Borodin等人在1995年得到的k=7.但是离Steinberg猜想还有较大距离. 本文在前人的工作基础上,运用延拓性引理和Discharge、粘点收缩偶面等方法,继续研究平面图的3可染色和3可选择性问题,证明了: (1)每一个不含4,6,7,9圈的平面图是3可选择的; (2)每一个不含4,5,8,9圈的平面图是3可选择的; (3)每一个不含4,7,9圈的平面图是3可染色的.
其他文献
心理素质是钢琴演奏者在舞台上应该具备的最基本的涵养,面对钢琴演奏这项复杂而高雅的器乐舞台表演艺术形式,演奏者不但要具备高超的钢琴演奏技巧,还应该拥有良好的心理素质.
金融系统是一个复杂的非线性系统,当受到外界因素干扰时,系统本身的内在不稳定性会导致混沌现象,产生难以预测的经济行为,因此对混沌金融系统的稳定性及控制和同步的理论研究
本文主要研究了以下三个问题:  1.右可逆系统{C,A,B}的解耦和极点配置问题。通过研究与系统相关的矩阵的秩的关系式,得到系统是右可逆的充要条件。给出右可逆系统的一种新的标准
字母教学是小学英语教学基础中的基础,关键中的关键.能否写出一手漂亮、规范的英语字母,对学生后续的英语学习将产生不可忽视的作用.另外,字母教学中如何渗透语音教学,与自然
随着科学技术的不断发展,带有边值条件的非线性常微分方程一直广泛应用于应用数学、物理、化学等领域,因此求解带有边值条件的非线性常微分方程有着很重要的现实意义,所以这
学位
经典的Cox模型是一种半参数的模型,要求协变量满足比例风险性的假设,这个要求过于苛刻。带有时间协变量的Cox模型不受比例风险性的约束,但是没有考虑到现实中未被观测到的因素对
多层中心网络是现实世界中一类比较典型的网络,本论文研究具有多层中心网络的各种性质及动力学行为。由于三层中心的网络是一种比一层和两层中心网络更重要更具代表性的多层中
数字图像在获取和传输的过程中常常会受到噪声的污染,噪声导致图像降质和丢失部分细节信息,能否有效地去除噪声对后续处理如图像分割、边缘检测等至关重要。然而实际应用中,
40年前,Monod和Jacob大胆预测:基本的细胞过程(如异化、蛋白质调控、代谢过程等)是通过基因水平上的信号通路来完成的,这种预测为描述许多细化的、基因水平上的重要调控机制奠定了