Ramsey equivalence of Kn and Kn + Kn−1

<p>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].</p&...

Full description

Bibliographic Details
Main Authors: Bloom, TF, Liebenau, A
Format: Journal article
Language:English
Published: Electronic Journal of Combinatorics 2018
_version_ 1826291721315549184
author Bloom, TF
Liebenau, A
author_facet Bloom, TF
Liebenau, A
author_sort Bloom, TF
collection OXFORD
description <p>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].</p> <p>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.</p>
first_indexed 2024-03-07T03:03:41Z
format Journal article
id oxford-uuid:b1cb0f7f-1e68-4a02-8abe-52b30768c9c8
institution University of Oxford
language English
last_indexed 2024-03-07T03:03:41Z
publishDate 2018
publisher Electronic Journal of Combinatorics
record_format dspace
spelling oxford-uuid:b1cb0f7f-1e68-4a02-8abe-52b30768c9c82022-03-27T04:06:48ZRamsey equivalence of Kn and Kn + Kn−1Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:b1cb0f7f-1e68-4a02-8abe-52b30768c9c8EnglishSymplectic ElementsElectronic Journal of Combinatorics2018Bloom, TFLiebenau, A<p>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].</p> <p>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.</p>
spellingShingle Bloom, TF
Liebenau, A
Ramsey equivalence of Kn and Kn + Kn−1
title Ramsey equivalence of Kn and Kn + Kn−1
title_full Ramsey equivalence of Kn and Kn + Kn−1
title_fullStr Ramsey equivalence of Kn and Kn + Kn−1
title_full_unstemmed Ramsey equivalence of Kn and Kn + Kn−1
title_short Ramsey equivalence of Kn and Kn + Kn−1
title_sort ramsey equivalence of kn and kn kn 1
work_keys_str_mv AT bloomtf ramseyequivalenceofknandknkn1
AT liebenaua ramseyequivalenceofknandknkn1