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

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) \geq 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.