Abstract
A graph F is Ramsey for a pair of graphs (G,H) if any red/blue-coloring of the edges of F yields a copy of G with all edges colored red or a copy of H with all edges colored blue. Two pairs of graphs are called Ramsey equivalent if they have the same collection of Ramsey graphs. The symmetric setting, that is, the case G=H, received considerable attention. This led to the open question whether there are connected graphs G and G′ such that (G,G) and (G′,G′) are Ramsey equivalent. We make progress on the asymmetric version of this question and identify several non-trivial families of Ramsey equivalent pairs of connected graphs.
Certain pairs of stars provide a first, albeit trivial, example of Ramsey equivalent pairs of connected graphs. Our first result characterizes all Ramsey equivalent pairs of stars. The rest of the paper focuses on pairs of the form (T,Kt), where T is a tree and Kt is a complete graph. We show that, if T belongs to a certain family of trees, including all non-trivial stars, then (T,Kt) is Ramsey equivalent to a family of pairs of the form (T,H), where H is obtained from Kt by attaching disjoint smaller cliques to some of its vertices. In addition, we establish that for (T,H) to be Ramsey equivalent to (T,Kt), H must have roughly this form. On the other hand, we prove that for many other trees T, including all odd-diameter trees, (T,Kt) is not equivalent to any such pair, not even to the pair (T,Kt⋅K2), where Kt⋅K2 is a complete graph Kt with a single edge attached.
Certain pairs of stars provide a first, albeit trivial, example of Ramsey equivalent pairs of connected graphs. Our first result characterizes all Ramsey equivalent pairs of stars. The rest of the paper focuses on pairs of the form (T,Kt), where T is a tree and Kt is a complete graph. We show that, if T belongs to a certain family of trees, including all non-trivial stars, then (T,Kt) is Ramsey equivalent to a family of pairs of the form (T,H), where H is obtained from Kt by attaching disjoint smaller cliques to some of its vertices. In addition, we establish that for (T,H) to be Ramsey equivalent to (T,Kt), H must have roughly this form. On the other hand, we prove that for many other trees T, including all odd-diameter trees, (T,Kt) is not equivalent to any such pair, not even to the pair (T,Kt⋅K2), where Kt⋅K2 is a complete graph Kt with a single edge attached.
Original language | English |
---|---|
Pages (from-to) | 55-74 |
Number of pages | 20 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 38 |
Issue number | 1 |
Early online date | 4 Jan 2024 |
DOIs | |
Publication status | Published - Mar 2024 |
Bibliographical note
Funding:The first author was supported by the Deutsche Forschungsgemeinschaft (DFG) Graduiertenkolleg "Facets of Complexity" (GRK 2434).
Keywords
- graph Ramsey theory
- Ramsey equivalence