Separation Between Higher Graph Equivalence Levels

Definitions and mathematical statement

The supplied record does not define its graph category or the term $q$-equivalent. The following formulation uses the usual edge-Ramsey interpretation, provisionally taking all graphs to be finite, simple, and undirected, with copies understood as subgraphs rather than induced subgraphs. These conventions require confirmation against the source; no connectedness or absence of isolated vertices is assumed unless stated explicitly.

For an integer $q\geq 2$, write $[q]=\{1,\ldots,q\}$. For graphs $G$ and $H$, define $G\longrightarrow_q H$ to mean that every edge-coloring $c:E(G)\to[q]$ admits an injective map $f:V(H)\to V(G)$ and a color $i\in[q]$ such that \[ \{f(u),f(v)\}\in E(G) \quad\text{and}\quad c(\{f(u),f(v)\})=i \qquad\text{for every }\{u,v\}\in E(H). \] The coloring need not use every color. Define $q$-Ramsey equivalence by \[ H\sim_q H' \quad\Longleftrightarrow\quad \forall G\;\left(G\longrightarrow_q H\ \Longleftrightarrow\ G\longrightarrow_q H'\right), \] where $G$ ranges over the provisional graph category above.

Under these conventions, the source asks:

1. Does \[ \forall H,H'\;\left(H\sim_2 H'\ \Longrightarrow\ H\sim_3 H'\right) \] hold?
2. Do there exist graphs $H,H'$ such that \[ H\sim_{100}H' \qquad\text{and}\qquad H\not\sim_{101}H'? \] Here $H\not\sim_{101}H'$ means that some graph $G$ satisfies exactly one of $G\longrightarrow_{101}H$ and $G\longrightarrow_{101}H'$.
3. The source reports known pairs satisfying $H\sim_3 H'$ and $H\not\sim_2 H'$ in which at least one graph is disconnected, and asks whether this is coincidental. A precise possible interpretation is whether there exist connected graphs $H,H'$ satisfying \[ H\sim_3 H'\qquad\text{and}\qquad H\not\sim_2 H'. \] The source's explanatory question does not explicitly specify this existential target, so this interpretation remains provisional.

The supplied record labels the problem open and reports the existence of the mentioned known pairs; these are supplied source claims, not independently verified conclusions.

Short English statement

Under the provisional edge-Ramsey interpretation, two graphs are $q$-equivalent when exactly the same host graphs force a monochromatic copy of either graph in every $q$-coloring of their edges. The questions concern whether equivalence for two colors implies equivalence for three, whether equivalence for $100$ colors can fail for $101$, and whether connected graphs can exhibit equivalence for three colors but failure for two. The graph conventions and the precise intended meaning of the final question require source confirmation.

Sources

• Supplied local UnsolvedMath registry record: permanent ID 30004035, title Separation Between Higher Graph Equivalence Levels, source problem code catalogue entry, collection Oberwolfach Reports Open Problems. The record gives proposed year 2019 and identifies no individual proposer.
• Supplied source citation: Graph Theory (2020), Oberwolfach Reports, pp. 5--63, DOI 10.4171/owr/2019/1: https://doi.org/10.4171/owr/2019/1. The background describes Oberwolfach Reports as documenting mathematical workshops and their open-problem discussions. The literature list calls this source Oberwolfach Report 1/2019; the supplied year descriptions require reconciliation.
• Clemens, Liebenau, and Reding, Ramsey equivalence: https://arxiv.org/abs/1809.09232.
• Conditions on Ramsey Nonequivalence: https://doi.org/10.1002/jgt.22119. The supplied record gives no authors for this reference.
• Supplied literature assessment, checked 2026-08-22: status open; known equivalences in two colors do not settle the proposed $100$ versus $101$ case, and the general Ramsey-equivalence question remains open. This is supplied dated curation derived from the OWR material, not an independently verified literature assessment. The source explicitly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and says that mathematical content was preserved while notation, typography, duplicate clauses, or omitted definitions were repaired. This supplied editorial qualification does not constitute independent mathematical review of this draft or verification of the cited sources.