The Study On Coloring Extremal Problems

An edge-colored graph is called rainbow,if all of its edges have different colors.While an edge-colored graph is called properly colored,if any two adjacent edges of it have different colors.The anti-Ramsey number of a graph H in a graph G,denoted by ar(G,H),is the maximum number of colors in an edge-colored G with no rainbow copy of H.The generalized anti-Ramsey number of a graph H in a graph G,denoted by pr(G,H),is the maximum number of colors in an edge-colored G with no properly colored copy of H.The anti-Ramsey number was first studied by Erd(?)s et al.in 1973.Since then,the researchers carried out extensive study for anti-Ramsey numbers of many graphs in the complete graphs.Also,the anti-Ramsey numbers have been generalized to various types.In this thesis,we will study the color number conditions for the existences of some rainbow(or properly colored)graphs in edge-colored complete graphs and complete r-partite graphs respectively,and the color number conditions for rainbow matchings in edge-colored complete r-partite r-uniform hypergraph and some sufficient conditions for the existence of a perfect matching in r-partite r-uniform hypergraphs and 3-uniform hm-bipartite hypergraphs respectively.The main results of this thesis are as follows:1.For sufficiently large n,we determine the exact value of the anti-Ramsey num-bers of star forests and double stars in K_nand the approximate value of the anti-Ramsey numbers of linear forests in the complete graphs respectively.2.We determine the exact value of the anti-Ramsey numbers of C₃and C₄in the complete r-partite graphs respectively.3.We show the relationship between the generalized anti-Ramsey numbers and Tur(?)n numbers.For sufficiently large l and n,we determine the exact values of the gen-eralized anti-Ramsey numbers of P_lin K_n.Furthermore,we determine the exact value of the generalized anti-Ramsey numbers of C₅,C₆and K ₄in the complete graphs re-spectively and give a lower bound and an upper bound of the generalized anti-Ramsey numbers of K_2,3in the complete graphs.4.We determine the exact value of the anti-Ramsey number of matchings in the complete r-partite r-uniform hypergraphs where the numbers of vertex in each parts are sufficiently large.5.We obtain a degree sum condition for the existence of a perfect matching in r-partite r-uniform hypergraphs.6.We obtain a degree condition for the existence of a perfect matching in 3-uniform hm-bipartite hypergraphs.