Publisher URL:
Publisher DOI: 10.1017/S0963548320000036
Title: On minimal Ramsey graphs and Ramsey equivalence in multiple colours
Language: English
Authors: Clemens, Dennis  
Liebenau, Anita 
Reding, Damian 
Keywords: Mathematics - Combinatorics; Mathematics - Combinatorics; 05D10
Issue Date: 2020
Source: Combinatorics, probability & computing 29: 537-554 (2020)
Abstract (english): 
For an integer q≥ 2, a graph G is called q-Ramsey for a graph H if every q-colouring of the edges of G contains a monochromatic copy of H. If G is q-Ramsey for H, yet no proper subgraph of G has this property then G is called q-Ramsey-minimal for H. Generalising a statement by Burr, Nešetřil and Rödl from 1977 we prove that, for q≥ 3, if G is a graph that is not q-Ramsey for some graph H then G is contained as an induced subgraph in an infinite number of q-Ramsey-minimal graphs for H, as long as H is 3-connected or isomorphic to the triangle. For such H, the following are some consequences. (1) For 2≤ r< q, every r-Ramsey-minimal graph for H is contained as an induced subgraph in an infinite number of q-Ramsey-minimal graphs for H. (2) For every q≥ 3, there are q-Ramsey-minimal graphs for H of arbitrarily large maximum degree, genus, and chromatic number. (3) The collection { 𝓜q(H) : H is 3-connected or K₃} forms an antichain with respect to the subset relation, where 𝓜q(H) denotes the set of all graphs that are q-Ramsey-minimal for H. We also address the question which pairs of graphs satisfy 𝓜q(H₁)= 𝓜q(H₂), in which case H₁ and H₂ are called q-equivalent. We show that two graphs H₁ and H₂ are q-equivalent for even q if they are 2-equivalent, and that in general q-equivalence for some q≥ 3 does not necessarily imply 2-equivalence. Finally we indicate that for connected graphs this implication may hold: Results by Nešetřil and Rödl and by Fox, Grinshpun, Liebenau, Person and Szabó imply that the complete graph is not 2-equivalent to any other connected graph. We prove that this is the case for an arbitrary number of colours.
ISSN: 0963-5483
Journal: Combinatorics, probability & computing 
Institute: Mathematik E-10 
Document Type: Article
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on Jul 5, 2022


Last Week
Last month
checked on Jun 30, 2022

Google ScholarTM


Add Files to Item

Note about this record

Cite this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.