Verlagslink: http://arxiv.org/abs/1809.09232v2 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, Nešetřil and Rö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 Nešetřil and Rödl and by Fox, Grinshpun, Liebenau, Person and Szabó 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. URI: http://hdl.handle.net/11420/7670 ISSN: 0963-5483 Zeitschrift: Combinatorics, probability & computing Institut: Mathematik E-10 Dokumenttyp: Artikel/Aufsatz Enthalten in den Sammlungen: Publications without fulltext

#### Seitenansichten

111
Letzte Woche
1
Letzten Monat
0
checked on 04.10.2022

#### SCOPUSTM Zitate

1
Letzte Woche
0
Letzten Monat
0
checked on 30.06.2022 