On Some Ramsey and Turán-Type Numbers for Paths and Cycles
Authors:
- Tomasz DzidoTDTomasz Dzido
- Marek KubaleMKMarek Kubale
- Konrad PiwakowskiKPKonrad Piwakowski
Open Access
- 7 January 2006
- journal article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 13 (1) , R55
Abstract
For given graphs $G_{1}, G_{2}, ... , G_{k}$, where $k \geq 2$, the multicolor Ramsey number $R(G_{1}, G_{2}, ... , 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, there is always a monochromatic copy of $G_{i}$ colored with $i$, for some $1 \leq i \leq k$. Let $P_k$ (resp. $C_k$) be the path (resp. cycle) on $k$ vertices. In the paper we show that $R(P_3,C_k,C_k)=R(C_k,C_k)=2k-1$ for odd $k$. In addition, we provide the exact values for Ramsey numbers $R(P_{4}, P_{4}, C_{k})=k+2$ and $R(P_{3}, P_{5}, C_{k})=k+1$.
Keywords
This publication has 7 references indexed in Scilit:
- Multicolor Ramsey Numbers for Paths and CyclesDiscussiones Mathematicae Graph Theory, 2005
- A sufficient condition for all short cyclesDiscrete Applied Mathematics, 1997
- Maximal cycles in graphsDiscrete Mathematics, 1991
- Maximal circuits of graphs. IActa Mathematica Hungarica, 1976
- Path Ramsey numbers in multicoloringsJournal of Combinatorial Theory, Series B, 1975
- Ramsey numbers for cycles in graphsJournal of Combinatorial Theory, Series B, 1973
- Combinatorial Relations and Chromatic GraphsCanadian Journal of Mathematics, 1955