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&...
Main Authors: | , |
---|---|
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 |