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 \leq i \leq r\), then \(G\) is said to be \(r\)-colorable to \((H_1, H_2, \ldots, H_r)\). The multicolor Ramsey number \(R(H_1, H_2, \ldots, H_r)\) is the smallest integer \(n\) such that \(K_n\) is not \(r\)-colorable to \((H_1, H_2, \ldots, 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 \leq R_4( C_6) \leq 21\). We prove that \(R(C_5, C_4, C_4, C_4) = 19\) and \(18 \leq R(C_6, C_6, H_1, H_2) \leq 20\), where \(H_i\) are isomorphic to \(C_4\) or \(C_6\).