Verlagslink DOI: 10.1017/S0963548320000036
Titel: On minimal Ramsey graphs and Ramsey equivalence in multiple colours
Sprache: Englisch
Autor/Autorin: Clemens, Dennis  
Liebenau, Anita 
Reding, Damian 
Schlagwörter: Mathematics - Combinatorics; Mathematics - Combinatorics; 05D10
Erscheinungs­datum: 2020
Quellenangabe: Combinatorics, probability & computing 29: 537-554 (2020)
Zusammenfassung (englisch): 
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
Zeitschrift: Combinatorics, probability & computing 
Institut: Mathematik E-10 
Dokumenttyp: Artikel/Aufsatz
Enthalten in den Sammlungen:Publications without fulltext

Zur Langanzeige


Letzte Woche
Letzten Monat
checked on 04.10.2022


Letzte Woche
Letzten Monat
checked on 30.06.2022

Google ScholarTM


Volltext ergänzen

Feedback zu diesem Datensatz

Diesen Datensatz zitieren


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.