论文部分内容阅读
图论是以图为研究对象,图的结构和染色一直是图论研究的核心内容.现今,越来越多的学者把两者结合在一起进行研究,并且得到了许多有意义的成果.彩虹问题就是两者结合的典型问题之一.早在上世纪五六十年代,国内外一些学者就曾对彩虹问题做过相关研究.彩虹问题研究的内容非常丰富,包括彩虹路,彩虹圈,彩虹匹配等方面.其中,彩虹圈问题一直是众多学者们着力研究的方向.著名的Mantel定理给出了n阶图G含一个C的充分条件:e(G)≥[n2/4]+1.Rademacher(1941)在[14]中把这个结果进行了优化,证明了在相同情况下,图G包含至少[n/2]个C3.2014年Binlong Li和Bo Ning等人在[5]中利用Rademacher的结果证明了 Mantel定理的彩虹版本:若n(n≥3)阶边染色图G满足e(G)+c(G)>n(n+1)/2,则图G中含一个彩虹C3.2019年Shiya Fujita等人于[3]中对上述结果进行改进,通过对|CN(u)∪CN(v)|下界进行讨论(其中u,u为边染色图G中任意点对),把结果推广到k个彩虹C4及k个点不交的彩虹圈上.此外,[3]中最后提出问题:对任意正整数k,寻找最小整数f(k),使得所有满足条件e(G)+c(G)≥n(n+1)/2+f(k)的边染色图G中都存在至少kk个彩虹C.本文根据[3]、[5]中的结果和[3]中的问题,对边染色图中彩虹C3的个数进行研究.全文共分四章,主要内容如下:第一章,主要介绍本文的研究背景和研究意义,以及近些年来国内外图论学者们在这方面所得到的成果.通过对相关研究背景和研究现状的讨论,进一步阐述了本文研究工作的意义和价值.第二章,主要给出本文中出现的一些基本概念和符号.第三章,主要研究边染色图中彩虹C3的个数与其边数及色数之间的关系.在第一节中,主要对[3]中的问题进行研究,得到一个初步结果:对任意正整数k都有f(k)≤2(k-1);在第二节中,主要分别研究当kk=2,3时,满足e(G)+c(G)≥n(n+1)/2+(k-1)的n阶边染色图G中彩虹C3的存在情况;在第三节中,对[3]中的问题进一步研究并得出当k≥ 4且为整数时都有f(k)≤2k-4;在第四节中,主要通过引入图类Gk(k≥ 2且为整数)对f(k)进一步研究,得出f(k)≥ k-1,并据此对f(k)的精确值提出猜想.第四章,总结全文,并提出可以进一步思考的问题.