### Abstract

We prove that, for n ≥ 4, the graphs K_{n} and K_{n}+K_{n–1} are Ramsey equivalent. That is, if G is such that any red-blue colouring of its edges creates a monochromatic K_{n} then it must also possess a monochromatic K_{n}+K_{n–1}. This resolves a conjecture of Szabó, Zumstein, and Zürcher [10]. The result is tight in two directions. Firstly, it is known that K_{n} is not Ramsey equivalent to K_{n}+2K_{n–1}. Secondly, K_{3} is not Ramsey equivalent to K_{3}+K_{2}. We prove that any graph which witnesses this non-equivalence must contain K_{6} as a subgraph.

Original language | English |
---|---|

Article number | #P3.4 |

Number of pages | 12 |

Journal | Electronic Journal of Combinatorics |

Volume | 25 |

Issue number | 3 |

Early online date | 13 Jul 2018 |

Publication status | Published - 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

Bloom, T. F., & Liebenau, A. (2018). Ramsey equivalence of K

_{n}and K_{n}+ K_{n–1}.*Electronic Journal of Combinatorics*,*25*(3), [#P3.4]. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p4