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, 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.
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

Zur Langanzeige

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

Google ScholarTM

Prüfe

Volltext ergänzen

Feedback zu diesem Datensatz

Diesen Datensatz zitieren

Export

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.