On some Ramsey and Turán-type numbers for paths and cycles
The electronic journal of combinatorics, Tome 13 (2006)
Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website
Zbl EuDML
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$.
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
@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/}
}
Cité par Sources :