Ramsey equivalence of Kn and Kn + Kn–1

Thomas F. Bloom, Anita Liebenau

Research output: Contribution to journalArticle (Academic Journal)peer-review

4 Citations (Scopus)
98 Downloads (Pure)


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 [10]. 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.

Original languageEnglish
Article number#P3.4
Number of pages12
JournalElectronic Journal of Combinatorics
Issue number3
Early online date13 Jul 2018
Publication statusPublished - Sept 2018


  • Graph theory
  • Ramsey theory


Dive into the research topics of 'Ramsey equivalence of Kn and Kn + Kn–1'. Together they form a unique fingerprint.

Cite this