PDF

Discussiones Mathematicae Graph Theory 25(1-2) (2005) 57-65
DOI: https://doi.org/10.7151/dmgt.1260

MULTICOLOR RAMSEY NUMBERS FOR PATHS AND CYCLES

Tomasz Dzido

Department of Computer Science
University of Gdańsk
Wita Stwosza 57, 80-952 Gdańsk, Poland
e-mail: tdz@math.univ.gda.pl

Abstract

For given graphs G₁,G₂,☐,G_k, k ≥ 2, the multicolor Ramsey number R(G₁,G₂,☐,G_k) 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 G_i, for 1 ≤ i ≤ k. We give a lower bound for k-color Ramsey number R(C_m,C_m,☐,C_m), where m ≥ 8 is even and C_m is the cycle on m vertices. In addition, we provide exact values for Ramsey numbers R(P₃,C_m,C_p), where P₃ is the path on 3 vertices, and several values for R(P_l,P_m,C_p), 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.

2000 Mathematics Subject Classification: 05C15, 05C55.

References

[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(C4,C4,C4), 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(C7,C7,C7), 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(Cn,Cn,Cn) ≤ (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.

Received 30 October 2003
Revised 28 January 2005