Clemens, DennisDennisClemensLiebenau, AnitaAnitaLiebenauReding, DamianDamianReding2020-10-272020-10-272020Combinatorics, probability & computing 29: 537-554 (2020)http://hdl.handle.net/11420/7670For 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.en1469-216320204537554Cambridge Univ. PressMathematics - CombinatoricsMathematics - Combinatorics05D10Journal Article10.1017/S09635483200000361809.09232v2Other