Some Results On The Number Of Rainbow C₃ ’S In Edge-colored Graphs

Graph theory is based on graphs,the structure and coloring of graphs have al-ways been the core content of graph theory research.Nowadays,more and more scholars have combined the two to conduct research,and have obtained many mean-ingful results.The rainbow problem is one of the typical problems of the combination of the two.As early as the 1950s and 1960s,some scholars at home and abroad have done relevant research on the rainbow problem.The content of rainbow problem research is very rich,including rainbow roads,rainbow cycles,rainbow matching,etc.Among them,the rainbow cycle problem has always been the direction of many scholars’ efforts.The well-known Mantel theorem gives a sufficient condition for n-order graph G including a C3:e(G)≥[n2/4]+1.Rademacher(1941)optimized this result in[14],which proves that under the same circumstances,the graph G contains at least[n/2]C3’s.In 2014,Binlong Li,Bo Ning and others used the results of Rademacher in[5]to prove the rainbow version of the Mantel theorem:if the n-order(n≥3)edge-colored graph G satisfies e(G)+c(G)≥n(n+1)/2,then the graph contains a rainbow C3.In 2019,Shiya Fujita and others improved the result of the appeal in[3],by discussing the lower bounds of |CN(u)∪CN(v)|(where u,v is any point pair in an edge-colored graph G),and the results were generalized to k rainbow C4’s and k vertex-disjoint rainbow cycles.In addition,the final question in[3]:for any positive integer k,find the smallest integer f(k),make every edge-colored graph G that satisfies the condition e(G)+c(G)≥n(n+1)/2+f(k)has at least k rainbow C3 ’s.This article is based on the results in[3],[5]and the problem in[3],the number of rainbow C3 ’s in edge-colored graphs is studied.The full text is divided into four chapters,and the main contents are as follows:In the first chapter,mainly introduces the research background and significance of this article,as well as the results obtained by graph scholars at home and abroad in recent years.Through the discussion of related research background and research status,the significance and value of the research work in this paper are further ex-pounded.In the second chapter,mainly gives some basic concepts and symbols appearing in this article.In the third chapter,mainly study the relationship between the number of rain-bow C3’s in the edge-colored graph and its edge number and color number.In the first section,we mainly study the problem in[3]and get a preliminary result:for any positive integer k,f(k)≤2(k-1);in the second section,we mainly study when k=2,3,the existence of rainbow C3’s in n-order edge-colored graph G satisfying the condition e(G)+c(G)≥n(n+1)/2+(k-1);in the third section,further study the problem in[3]and conclude that when k≥4 and is an integer,there is always f(k)≤2k-4;in the fourth section,mainly through the introduction of graph Gk(k≥2 is an integer)to further study f(k),we get f(k)≥k-1,and based on this,we guess the exact value of f(k).In the fourth chapter,summarizes the full text,and proposes problems for further thinking.