Multicolor Ramsey numbers for paths and cycles

Tomasz Dzido

Discussiones Mathematicae Graph Theory (2005)

  • Volume: 25, Issue: 1-2, page 57-65
  • ISSN: 2083-5892

Abstract

top
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 G i , 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.

How to cite

top

Tomasz Dzido. "Multicolor Ramsey numbers for paths and cycles." Discussiones Mathematicae Graph Theory 25.1-2 (2005): 57-65. <http://eudml.org/doc/270242>.

@article{TomaszDzido2005,
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 $G_i$, 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.},
author = {Tomasz Dzido},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {edge coloring; Ramsey number},
language = {eng},
number = {1-2},
pages = {57-65},
title = {Multicolor Ramsey numbers for paths and cycles},
url = {http://eudml.org/doc/270242},
volume = {25},
year = {2005},
}

TY - JOUR
AU - Tomasz Dzido
TI - Multicolor Ramsey numbers for paths and cycles
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 1-2
SP - 57
EP - 65
AB - 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 $G_i$, 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.
LA - eng
KW - edge coloring; Ramsey number
UR - http://eudml.org/doc/270242
ER -

References

top
  1. [1] J. Arste, K. Klamroth and I. Mengersen, Three color Ramsey numbers for small graphs, Utilitas Mathematica 49 (1996) 85-96. Zbl0854.05077
  2. [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. Zbl0248.05127
  3. [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. Zbl0513.05040
  4. [4] C. Clapham, The Ramsey number R(C₄,C₄,C₄), Periodica Mathematica Hungarica 18 (1987) 317-318, doi: 10.1007/BF01848105. 
  5. [5] T. Dzido, Computer experience from calculating some 3-color Ramsey numbers (Technical Report of Gdańsk University of Technology ETI Faculty, 2003). 
  6. [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. [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. Zbl0064.17901
  8. [8] T. Łuczak, R(Cₙ,Cₙ,Cₙ) ≤ (4+o(1))n, J. Combin. Theory (B) 75 (1999) 174-187. 
  9. [9] S.P. Radziszowski, Small Ramsey numbers, Electronic J. Combin. Dynamic Survey 1, revision #9, July 2002, http://www.combinatorics.org/. Zbl0953.05048
  10. [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. Zbl0756.05078
  11. [11] P. Rowlison and Y. Yang, On Graphs without 6-cycles and related Ramsey numbers, Utilitas Mathematica 44 (1993) 192-196. Zbl0789.05070
  12. [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. Zbl0233.05117

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.