Ramsey equivalence of Kn and Kn + Kn–1

Thomas F. Bloom, Anita Liebenau

Research output: Contribution to journalArticle (Academic Journal)

2 Citations (Scopus)
59 Downloads (Pure)

Abstract

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
Volume25
Issue number3
Early online date13 Jul 2018
Publication statusPublished - Sep 2018

Keywords

  • Graph theory
  • Ramsey theory

Fingerprint Dive into the research topics of 'Ramsey equivalence of K<sub>n</sub> and K<sub>n</sub> + K<sub>n–1</sub>'. Together they form a unique fingerprint.

  • Cite this