Three color Ramsey numbers for graphs with at most 4 vertices
Summary: For given graphs \(H_{1}, H_{2}, H_{3}\), the 3-color Ramsey number \(R(H_{1},H_{2}, H_{3})\) is the smallest integer \(n\) such that if we arbitrarily color the edges of the complete graph of order \(n\) with 3 colors, then it always contains a monochromatic copy of \(H_{i}\) colored with \(i\), for some \(1 \leq i \leq 3\). We study the bounds on 3-color Ramsey numbers \(R(H_1,H_2,H_3)\), where \(H_i\) is an isolate-free graph different from \(K_2\) with at most four vertices, establishing that \(R(P_4,C_4,K_4) = 14\), \(R(C_4,K_3,K_4-e) = 17\), \(R(C_4,K_3+e,K_4-e) = 17\), \(R(C_4,K_4-e,K_4-e) = 19\), \(28\leq R(C_4,K_4-e,K_4) \leq 36\), \(R(K_3,K_4-e,K_4) \leq 41\), \(R(K_4-e,K_4-e,K_4) \leq 59\) and \(R(K_4-e,K_4,K_4) \leq 113\). Also, we prove that \(R(K_3+e,K_4-e,K_4-e) = R(K_3,K_4-e,K_4-e)\), \(R(C_4,K_3+e,K_4) \leq \max\{R(C_4,K_3,K_4),29\} \leq 32\), \(R(K_3+e,K_4-e,K_4) \leq \max\{R(K_3,K_4-e,K_4),33\} \leq 41\) and \(R(K_3+e,K_4,K_4)\leq \max\{R(K_3,K_4,K_4),2R(K_3,K_3,K_4)+2\} \leq79\). This paper is an extension of the article by \textit{J. Arste} et al. [Util. Math. 49, 85--96 (1996; Zbl 0854.05077)].
scientific article; zbMATH DE number 6171830