## 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_{n}and K

_{n}+ K

_{n–1}'. Together they form a unique fingerprint.