平面图的(d1,d2,d3)-染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:xufei037
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
论文中所考虑的图形只是简单,有限,无向图.令G=(V,E)是一个以V为顶点集,E为边集的图,并且k是一个非负整数.如果存在这样的一个映射φ:V→{1,2,…,k},使得对任意uv∈E,都有φ(u)≠φ(v),那么G就有一个k-染色φ,称G是一个k-可染的图.  令d1,d2,…,dk都是非负整数,并且G=(V,E)是一个可平面图.图G的一个(d1,d2,…,dk)-染色是指存在一个映射φ:V→{1,2,…,k},使得诱导子图G[Vi]的最大度至多为di,Vi={v∈V|φ(vi)=i}.如果G有一个(d1,d2,…,dk)-染色,那么称G是(d1,d2,…,dk)-可染的.如果d1=d2=…=dk=d,那么称G是d-非正常k-可染的,或是(k,d)*-可染的.  留意到G是正常k-可染的与G是(0,0,…,0)-可染的是等价的;对于di≥di,i={1,2,…,k},如果G是(d1,d2,…,dk)-可染的,那么它同时是(d1,d2,…,dk)-可染的.  Steinberg于1976年提出了一个著名的猜想:不含4-圈和5-圈的可平面图是3-可染的.直至2016年4月,Steinberg的猜想才被证明是错误的.在近四十多年的探索研究过程中,因Steinberg猜想有较大的难度,Erd(o)s认为可先放宽条件研究问题:能否可以找到一个正整数C(≥4l),使得不含4-圈到C-圈的平面图是3-可染的呢?围绕这一问题,众多专家,学者开展一系列相关研究,并取得了丰硕的成果.  本文一共分为三章内容,主要围绕上述的猜想及相关问题开展研究.第一章介绍了本文所涉及到的相关定义与符号,并阐述了关于(d1,d2,d3)-染色的研究现状.第二章介绍了关于(1,1,0)-染色的两个结果.第三章介绍关于(2,0,0)-染色的两个结果.
其他文献
风险理论是当前精算学和数学界研究的热门话题,作为保险精算的一部分,它主要是处理保险实务经营中的随机风险模型,并研究破产概率、调节系数等问题。本文研究了几类时间盈余风险
本文主要研究Carathéodory矩阵函数类中两类带边界插值数据的Nevanlinna-Pick插值问题.其中一类是非常著名的,已经有几种系统的解决方法,本文建立它与截断三角矩量问题之间的
本文主要对三类广义凸函数做了进一步研究。首先在一类重要的广义凸性—预不变凸性的基础上,提出了强预不变凸函数的概念。这类新的广义凸函数是预不变凸函数的一种特殊情况,也
本文主要讨论了弱test多项式,test多项式,强test多项式及坐标多项式的结构与性质,并简单的讨论了test元的性质,给出了一些新结果。 本文回顾了问题的由来,理论的形成与发展,给
经历了轰轰烈烈的新课改之后,目前的小学语文课堂发生了一些根本性的改变,传统教学模式已经消失,现代教育技术被越来越多地应用于课堂。因为现代教育技术具有强大的辅助作用,
本文研究了如下互利共生者与入侵者(P-M-E)模型的动力学性质:dP/dT=bpPM(1-M)(1E)(1P)PdM/dT=bMPM(1-μM)dMMdE/dT=bEPE(1-M)(1-αE)-dEE当没有入侵者即E=0时,讨论了有生物学意
本文研究维特环上的首一分量不为常数的多项式f(x)∈Wm(Fq[x±11,x±12,…,x±1n]),尤其是研究L-函数L(f,t)的总指数和在相同权数下L(f,t)的互反根个数目。通过应用p-进制分析及指
近年来,经济的发展使得房地产业变得越来越重要。随着房地产业的繁荣和房地产市场的进一步完善,如何客观、准确地评估房地产已成为人们普遍关注的问题。本文首先介绍了四种常见
非线性系统是实际中存在的一类复杂系统,无论在建模还是控制方面都具有相当的难度。对非线性系统,多模型是一种行之有效的建模与控制方法,它通过建立多个局部模型来实现对被控对
加强党内监督,是邓小平执政党建设和国家民主法制建设理论的一项内容。但是,它并非邓小平执政党党风建没和国家民主法制建设理论的全部。邓小平对马克思主义的重大发展、对