Research On Ramsey Number Of Some Graphs

Ramsey theory is an important subdiscipline of Discrete Mathematics, and graph Ramsey number is a main branch of Ramsey theory. There are many interesting applications of Ramsey theory. These include results in number theory, algebra, geometry, topology, set theory, logic, information theory and theoretical computer science. Determining generalized Ramsey numbers is NP-hard. Up to now, there are few exact values of Ramsey numbers which are known. The application of computer makes it become a presently most active area in Ramsey theory. Combining the computer constructive proof with mathematical proof, three subjects as the lower bound on R_r(C_2m), the three color Ramsey number R(C_m0, C_m1, C_m2) and the planar Ramsey number are researched in this dissertation. Some problems have been solved respectively.Graham, Rothschild and Spencer proved that R_r(C_2m)≥ (r - l)(m- 1) + 1 in Ramsey Theory in 1990. By two r-colorings of the edges of a complete graph, the lower bounds that R_r(C_2m) ≥ max{(r + 1)m -1 + (r mod 2), 2(r- 1)(m -1) + 2} are obtained in this paper. Especially for r = 3, R₃(C_2m) ≥ 4m. The known results show that the equality holds for m = 3 and 4.The values of R₃(C_m) for m ≤ 7 are known. An algorithm for constructing the critical graph not containing C_m and an algorithm for coloring the edges of a graph with two colors are given in this dissertation. Utilizing two algorithms, the result that R₃(C₈) = 16 is proved. The values of R(C_m0, C_m1, C_m2) for m₂≤ m₁ < m₀≤ 7 are also determined in this paper. Erdos, Faudree, Rousseau et al. proved that R(C_m, C₃, C₃) = 5m - 4 and R(C_m, C₄, C₄) = m + 2 for sufficiently large m in 1976. Their values in the case that m is not sufficiently large are studied in this dissertation. It is shown that R(C_m, C3, C3) = 5m - 4 for m≥ 5. By the above algorithms, the result that R(C_m, C₄, C₄) = m + 2 for m ≥ 11 are proved. And the values of R(C_m, C₄, C₄) for 5 ≤ m ≤ 10 are obtained in this dissertation.The definition of planar Ramsey number was firstly introduced by Walker in 1969. Bielak and Gorgol gave that PR(C₄, K₅) = 13, PR(C₄, K₆) = 17 and PR(C₄, K_l) > 3l + (?)(1 -1)/5(?) - 2 for l≥ 3. An algorithm for determining the planar Ramsey number of PR(H₁, H₂) is given in this dissertation. With the help of a computer, the results that PR(K₄ -e, K₅) = 14, PR(K₄- e, K₆)=l7 and PR(C₄, K₇) = 20 are obtained. The results that PR(K₄- e, K₅ ) = 14...