Three Color Ramsey Numbers for Graphs with at most 4 Vertices

Abstract

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\le R(C_4,K_4-e,K_4)\le36$, $R(K_3,K_4-e,K_4)\le41$, $R(K_4-e,K_4-e,K_4)\le59$ and $R(K_4-e,K_4,K_4)\le113$. 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)\le\max\{R(C_4,K_3,K_4),29\}\le32$, $R(K_3+e,K_4-e,K_4)\le\max\{R(K_3,K_4-e,K_4),33\}\le41$ and $R(K_3+e,K_4,K_4)\le\max\{R(K_3,K_4,K_4),2R(K_3,K_3,K_4)+2\}\le79$.This paper is an extension of the article by Arste, Klamroth, Mengersen [Utilitas Mathematica, 1996].

Locations

• The Electronic Journal of Combinatorics - View - PDF