A Conjecture of Erdés the Ramsey Number $r(W_6)$

Abstract

It was conjectured by Paul Erdős that if $G$ is a graph with chromatic number at least $k$, then the diagonal Ramsey number $r(G)\ge r(K_k)$. That is, the complete graph $K_k$ has the smallest diagonal Ramsey number among the graphs of chromatic number $k$. This conjecture is shown to be false for $k=4$ by verifying that $r(W_6)=17$, where $W_6$ is the wheel with $6$ vertices, since it is well known that $r(K_4)=18$. Computational techniques are used to determine $r(W_6)$ as well as the Ramsey numbers for other pairs of small order wheels.