ArticleOriginal scientific text

Title

Multicolor Ramsey numbers for paths and cycles

Authors 1

Affiliations

  1. Department of Computer Science, University of Gdańsk, Wita Stwosza 57, 80-952 Gdańsk, Poland

Abstract

For given graphs G₁,G₂,...,Gₖ, k ≥ 2, the multicolor Ramsey number R(G₁,G₂,...,Gₖ) is the smallest integer n such that if we arbitrarily color the edges of the complete graph on n vertices with k colors, then it is always a monochromatic copy of some Gi, for 1 ≤ i ≤ k. We give a lower bound for k-color Ramsey number R(Cₘ,Cₘ,...,Cₘ), where m ≥ 8 is even and Cₘ is the cycle on m vertices. In addition, we provide exact values for Ramsey numbers R(P₃,Cₘ,Cₚ), where P₃ is the path on 3 vertices, and several values for R(Pₗ,Pₘ,Cₚ), where l,m,p ≥ 2. In this paper we present new results in this field as well as some interesting conjectures.

Keywords

edge coloring, Ramsey number

Bibliography

  1. J. Arste, K. Klamroth and I. Mengersen, Three color Ramsey numbers for small graphs, Utilitas Mathematica 49 (1996) 85-96.
  2. J.A. Bondy and P. Erdös, Ramsey numbers for cycles in graphs, J. Combin. Theory (B) 14 (1973) 46-54, doi: 10.1016/S0095-8956(73)80005-X.
  3. A. Burr and P. Erdös, Generalizations of a Ramsey-theoretic result of Chvatal, J. Graph Theory 7 (1983) 39-51, doi: 10.1002/jgt.3190070106.
  4. C. Clapham, The Ramsey number R(C₄,C₄,C₄), Periodica Mathematica Hungarica 18 (1987) 317-318, doi: 10.1007/BF01848105.
  5. T. Dzido, Computer experience from calculating some 3-color Ramsey numbers (Technical Report of Gdańsk University of Technology ETI Faculty, 2003).
  6. R. Faudree, A. Schelten and I. Schiermeyer, The Ramsey number R(C₇,C₇,C₇), Discuss. Math. Graph Theory 23 (2003) 141-158, doi: 10.7151/dmgt.1191.
  7. R.E. Greenwood and A.M. Gleason, Combinatorial relations and chromatic graphs, Canadian J. Math. 7 (1955) 1-7, doi: 10.4153/CJM-1955-001-4.
  8. T. Łuczak, R(Cₙ,Cₙ,Cₙ) ≤ (4+o(1))n, J. Combin. Theory (B) 75 (1999) 174-187.
  9. S.P. Radziszowski, Small Ramsey numbers, Electronic J. Combin. Dynamic Survey 1, revision #9, July 2002, http://www.combinatorics.org/.
  10. P. Rowlison and Y. Yang, On the third Ramsey numbers of graphs with five edges, J. Combin. Math. and Combin. Comp. 11 (1992) 213-222.
  11. P. Rowlison and Y. Yang, On Graphs without 6-cycles and related Ramsey numbers, Utilitas Mathematica 44 (1993) 192-196.
  12. D.R. Woodall, Sufficient conditions for circuits in graphs, Proc. London Math. Soc. 24 (1972) 739-755, doi: 10.1112/plms/s3-24.4.739.
Pages:
57-65
Main language of publication
English
Received
2003-10-30
Accepted
2005-01-28
Published
2005
Exact and natural sciences