On some Ramsey and Turán-type numbers for paths and cycles
The electronic journal of combinatorics, Tome 13 (2006)
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$.
@article{10_37236_1081,
author = {Tomasz Dzido and Marek Kubale and Konrad Piwakowski},
title = {On some {Ramsey} and {Tur\'an-type} numbers for paths and cycles},
journal = {The electronic journal of combinatorics},
year = {2006},
volume = {13},
doi = {10.37236/1081},
zbl = {1098.05054},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1081/}
}
Tomasz Dzido; Marek Kubale; Konrad Piwakowski. On some Ramsey and Turán-type numbers for paths and cycles. The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1081
Cité par Sources :