On the Four Color Ramsey Numbers for Hexagons

Abstract

Let $G_i$ be the subgraph of $G$ whose edges are in the $i$-th color in an $r$-coloring of the edges of $G$. If there exists an $r$-coloring of the edges of $G$ such that $H_i\cong G_i$ for all $1\le i\le r$, then $G$ is said to be $r$-colorable to $(H_1,H_2,\dots ,H_r)$. The multicolor Ramsey number $R(H_1,H_2,\dots ,H_r)$ is the smallest integer $n$ such that $K_n$ is not $r$-colorable to $(H_1,H_2,\dots ,H_r)$. Let $C_m$ be a cycle of length $m$. The four-color Ramsey numbers related to $C_6$ are studied in this paper. It is well known that $18\le R_4(C_6)\le 21$. We prove that $R(C_5,C_4,C_4,C_4)=19$ and $18\le R(C_6,C_6,H_1,H_2)\le 20$, where $H_i$ are isomorphic to $C_4$ or $C_6$.