平面图的3-染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:play11200
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
用G=(V,E,F)表示一个以V为顶点集,E为边集,F为面集的平面图.著名的四色定理告诉我们:每个平面图是4色可染的,之后人们的研究兴趣自然转移到平面图的3-染色问题上来.早在1959年,Gr(o)tzsch证明了第一个三色定理:不含3-圈的平面图是3色可染的.1970年,Havel提出问题:是否存在常数k使得三角形距离至少是k的平面图是3色可染的?有关3-染色的另一个著名问题是由Steinberg在1976年提出来的,又称为Steinberg猜想:既不含4-圈又不含5-圈的平面图是3色可染的.鉴于Steinberg猜想历经很久而无进展,在1991年,Erd(o)s建议研究这样一个问题:是否存在一个正整数k使得不包含4-至k-圈的平面图都是3色可染的?就在1991年,Abbott和Zhou证明了这样的k确实存在,且k≤11.之后Borodin,Sanders和Zhao,分别独立地改进k值到9.接着Borodin等人再一次将k值降到了7.近期的一系列研究已表明:没有4-,j-,k-,l-圈的平面图是3色可染的,其中5≤j≤k≤l≤9.这是研究平面图3色可染问题的一个阶段性成果.  接下来的问题自然是去研究含有3-圈但不含有4-,j-,k-圈的平面图的3色可染问题,这里5≤j≤k.许宝刚,Borodin等人各自独立地证明了既没有相邻三角形,又没有5-,7-圈的平面图是3色可染的.作为这一结果的推论,没有4-,5-,7-圈的平面图是3色可染的.本文证明一个比此推论更接近Steinberg猜想的结果.在第二章证明了:设G是一个既没有4-圈又没有5-圈的平面图,若对每一个k∈{3,6,7},G都不含(k,7)-弦,则G是3色可染的,这里的(k,7)-弦是指长度为7+k-2的圈的一条弦,它的两个端点将圈分成两条路,一条路的长度为6,另一条路的长度为k-1.  结合Havel提出的问题以及Steinberg猜想,在2003年,Borodin和Raspaud提出了著名的Bordeux猜想:既不含5-圈又不含相交(相邻)三角形的平面图是3色可染的.关于此猜想的首次突破是:不含5-圈且三角形距离至少是4的平面图是3色可染的.接下来,这一结果在2004年和2007年,分别由Borodin,Glebov,和许宝刚独立的改进到不含5-圈且三角形距离至少是3的平面图是3色可染的,之后Borodin和Glebov在2010年把距离改进到小于等于2.在研究3-染色的问题中,大多讨论的是不含某些特殊的圈,是否可以去研究圈都存在而限定圈的距离呢?因此,Montassier等人证明每一个不含距离小于等于4的5--圈的可平面图是3色可染的.Borodin,Montassier和Raspaud进一步提出:不含相邻5--圈的平面图是否是3色可染的?本文在第三章证明了:不含距离小于等于2的5--圈的平面图是3色可染的.  在探索不含4-,j-,k-圈(5≤ j≤k)的平面图的3色可染问题的过程中,首次研究这一问题并取得重要结果的是许宝刚教授,证明了没有相邻三角形且没有5-,7-圈的平面图是3色可染的(这一结果也被国际著名染色理论专家Borodin等人用不同的方法所证明).显然,这一结果比此前的所有结果更为逼近Steinberg猜想,作为它的推论,人们得到没有3种长度圈的平面图是3色可染的第一个肯定性结果,即没有4-,5-,7-圈的平面图是3色可染的.该方向的第二,第三个正面肯定结果分别由王维凡,陈敏和陆华晶,王应前获得,即没有4-,6-,8-圈和4-,7-,9-圈的平面图是3色可染的.除了上述3个正面结果外,还没有发现任何其它的有关含有三角形但不含有4-圈和另外两种长度圈的平面图是或不是3色可染的正确命题.本文第四章就是在之前的研究基础上,证明了第四个正面的结果:不含4-,6-,9-圈的平面图是3色可染的.
其他文献
本文研究有限简单图.图G的一个injecdve k-染色是指映射φ:V(G)→{1,2,….,k},使得G中有公共邻点的两个顶点u,v满足φ(u)≠φ(v).如果图G有一个injectivek-染色,则称图G是injectivek
学位
复杂系统是由若干个子系统按照特定方式组成,因此复杂系统可靠度受到其子系统的数量、质量、类型以及连接方式直接影响.在可靠性分析中,理想状态的系统寿命数据包括两方面:失效
在许多领域中,数学物理反问题都有着广泛而重要的应用,且理论新颖、富有挑战性.反问题通常为不适定问题,这是因为数学物理反问题在求解的过程中存在两个本质性的实际问题:一为解
学位
本文主要讨论了地震数据处理中的偏移成像问题。为了提高计算效率,利用波动方程算子的性质合成了炮震源以及炮记录并且采用了并行算法。另外还采用了高阶差分来求解波动方程,
本文运用Bellman不等式,解的存在唯一性定理,压缩映射定理,Ascoli-Arzela定理和Mawhin重合度理论等多种理论,研究了二类微分方程的拓扑线性化及一类食草动物模型周期解的存在性问
2000年Branciari在度量空间的基础上,用四角不等式代替三角不等式提出了矩度量空间的概念,并证明了Banach压缩映象的不动点定理.随后,许多学者将矩度量空间推广为偏矩度量、锥矩