We study the multicolor Ramsey numbers for paths and even cycles, $R_k(P_n)$ and $R_k(C_n)$, which are the smallest integers $N$ such that every coloring of the complete graph $K_N$ has a monochromatic copy of $P_n$ or $C_n$ respectively. For a long time, $R_k(P_n)$ has only been known to lie between $(k-1+o(1))n$ and $(k + o(1))n$. A recent breakthrough by Sárközy and later improvement by Davies, Jenssen and Roberts give an upper bound of $(k - \frac{1}{4} + o(1))n$. We improve the upper bound to $(k - \frac{1}{2}+ o(1))n$. Our approach uses structural insights in connected graphs without a large matching.
@article{10_37236_7614,
author = {Charlotte Knierim and Pascal Su},
title = {Improved bounds on the multicolor {Ramsey} numbers of paths and even cycles},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {1},
doi = {10.37236/7614},
zbl = {1409.05088},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7614/}
}
TY - JOUR
AU - Charlotte Knierim
AU - Pascal Su
TI - Improved bounds on the multicolor Ramsey numbers of paths and even cycles
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/7614/
DO - 10.37236/7614
ID - 10_37236_7614
ER -
%0 Journal Article
%A Charlotte Knierim
%A Pascal Su
%T Improved bounds on the multicolor Ramsey numbers of paths and even cycles
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/7614/
%R 10.37236/7614
%F 10_37236_7614
Charlotte Knierim; Pascal Su. Improved bounds on the multicolor Ramsey numbers of paths and even cycles. The electronic journal of combinatorics, Tome 26 (2019) no. 1. doi: 10.37236/7614
