论文部分内容阅读
用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色可染的.