Font Size: a A A

Three Color Ramsey Numbers R(Cm1,Cm2,Cm3)

Posted on:2007-07-01Degree:MasterType:Thesis
Country:ChinaCandidate:W WangFull Text:PDF
GTID:2178360182460962Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
Ramsey theory constitutes the main research area of graph theory, and 3-coloring Ramsey theory is an important branch of Ramsey theory, the determination of 3-coloring Ramsey number is also an important research direction of Ramsey theory, and it is meanwhile a No-Polynomial Problem. Ramsey theory has great theoretical significance in the evolution of mathematics, however, we only obtained a few of 3-coloring Ramsey numbers so far.Let Gi be the subgraph of G whose edges are in the i -th color in an r -coloring of theedges of G . If there exists a r -coloring of the edges of G such that forbidden subgraph Hi (?) Gi, for all 1≤i≤r, then G is said to be r-colorable to(H1,H2,...,Hr). The multicolorRamsey number R(H1H2,...,Hr) is the smallest integer n such that Kn is not r-colorable to(H1,H2,...,Hr). The Ramsey number R(Cm1,Cm2,Cm3) is studied in this paper, where r = 3and H(?) C.Erd6s proved that R{Cm, C3, C3) = 5m - 4 and R(Cm, C4, C4) = m + 2 when m is sufficiently large.The paper proves that R(Cm,C3,C3) = 5m-4 when m≥5; When m1, is not sufficientlylarge and 7≥m1>m2l≥m3, this paper uses the concept of critical graph to obtain all the values of Ramsey number R(Cm1,Cm2,Cm3), meanwhile gives a conjecture. After giving a new definition of critical graph, this paper also obtains all the values of Ramsey number R(Cm,C4, C4), what is R(Cm,C4,C4) = m + 2 when 11≤m≤19, and also prove that R(Cm,C4,C4) =m + 2 when m>19.
Keywords/Search Tags:Edge Coloring, Multicolor Ramsey Number, Critical Graph, Forbidden Subgraph, Cycles
PDF Full Text Request
Related items