Equivalence Hierarchies for Connected Graphs

Definitions and mathematical statement

The supplied record does not explicitly define its graph conventions, $q$-equivalence, the operation $+$, or unqualified Ramsey equivalence. The following is a conditional formalization under the usual edge-Ramsey interpretation; these conventions require confirmation against the cited sources.

Take graphs to be finite, simple, and undirected. For graphs $G,F$ and an integer $q\geq2$, write \[ G\longrightarrow(F)_q \] if every map $c:E(G)\to\{1,\ldots,q\}$ admits a subgraph of $G$ isomorphic to $F$ whose edges all receive the same color. Copies are not required to be induced, and the coloring need not use every color. Define \[ F\sim_q F' \quad\Longleftrightarrow\quad \text{for every finite simple undirected graph }G, \quad G\longrightarrow(F)_q\ \Longleftrightarrow\ G\longrightarrow(F')_q. \] Under this interpretation, $q$-equivalent means related by $\sim_q$. A graph is connected if it has at least one vertex and every two vertices are joined by a path. Write $F\not\cong F'$ when the graphs are not isomorphic. Let $K_k$ be the complete graph on $k$ vertices. Interpret $K_k+H$ as the disjoint union of $K_k$ and $H$, with no edges between the two components, and interpret unqualified Ramsey equivalence as $\sim_2$.

With these conventions, the supplied questions are:

1. Is it true that, for every pair of connected graphs $H,H'$, \[ H\sim_3 H'\quad\Longrightarrow\quad H\sim_2 H'? \]
2. Is it true that \[ \forall q\in{\mathbb{Z}},\ q\geq2,\quad \exists\text{ connected graphs }H,H' \quad\text{such that}\quad H\not\cong H'\ \text{ and }\ H\sim_q H'? \] The graphs may depend on $q$; the wording does not require one pair to work for every $q$.
3. For a fixed parameter $k$, characterize the graphs $H$ for which \[ K_k\sim_2(K_k+H), \] or, equivalently, for which every finite simple undirected graph $G$ satisfies \[ G\longrightarrow(K_k)_2 \quad\Longleftrightarrow\quad G\longrightarrow(K_k+H)_2. \]

The last question does not explicitly restrict $H$ to connected graphs. The source supplies neither the intended range of $k$ nor a restriction excluding the empty graph as $H$; these boundary conditions remain unresolved. The notation $K_k$ ordinarily requires a nonnegative integer vertex count, but no intended lower bound is inferred here. If $+$ denotes a join, or if unqualified Ramsey equivalence refers to a different color quantifier, the third question must be reformulated accordingly.

Short English statement

Under the explicitly provisional edge-Ramsey conventions, ask whether connected graphs equivalent for three colors must be equivalent for two, whether each integer $q\geq2$ admits nonisomorphic connected $q$-equivalent graphs, and which graphs can be added disjointly to $K_k$ without changing its two-color Ramsey equivalence class. The intended graph conventions, meaning of $+$, color convention in the final question, and range of $k$ require source confirmation. The supplied open status is dated curation, not an independently verified conclusion.

Sources

• Local registry: data/unsolvedmath/problems.json, supplied record with permanent UnsolvedMath ID $30004036$, title "Equivalence Hierarchies for Connected Graphs," exact source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record lists proposed year $2019$ and supplies no individual proposer.
• Supplied report citation: Graph Theory (2020), Oberwolfach Reports, DOI 10.4171/owr/2019/1, pp. 5--63. https://doi.org/10.4171/owr/2019/1. The literature-source entry labels this "Oberwolfach Report 1/2019." The report title's year and the report identifier's year are retained as supplied.
• Supplied literature reference: Clemens, Liebenau, and Reding, Ramsey equivalence. https://arxiv.org/abs/1809.09232.
• Literature assessment dated exactly 2026-08-22: the supplied record labels the problem open and states that the connected-graph implication and classification of further $q$-equivalent graph pairs remain open in the cited literature. This is supplied dated curation, described in the background as literature triage derived from the supplied OWR curation; it has not been independently verified. The record expressly calls for independent verification of time-sensitive status and cited claims.
• The supplied registry labels the statement corrected_verified and says its mathematical content was preserved while notation, typography, duplicate clauses, or omitted definitions were repaired for self-contained publication. This is a supplied verification claim, not mathematical verification of this draft or confirmation of the conventions used above.