We prove that, for n ≥ 4, the graphs Kn and Kn+Kn–1 are Ramsey equivalent. That is, if G is such that any red-blue colouring of its edges creates a monochromatic Kn then it must also possess a monochromatic Kn+Kn–1. This resolves a conjecture of Szabó, Zumstein, and Zürcher . The result is tight in two directions. Firstly, it is known that Kn is not Ramsey equivalent to Kn+2Kn–1. Secondly, K3 is not Ramsey equivalent to K3+K2. We prove that any graph which witnesses this non-equivalence must contain K6 as a subgraph.
|Number of pages||12|
|Journal||Electronic Journal of Combinatorics|
|Early online date||13 Jul 2018|
|Publication status||Published - Sep 2018|
- Graph theory
- Ramsey theory