Computing Transversality Degrees of Graphs

Definitions and mathematical statement

A median graph is a connected simple undirected graph $M$ such that, for every $x,y,z\in V(M)$, the intersection \[ I_M(x,y)\cap I_M(y,z)\cap I_M(z,x) \] contains exactly one vertex, where \[ I_M(u,v)=\{w\in V(M):d_M(u,w)+d_M(w,v)=d_M(u,v)\} \] and $d_M$ is the unweighted graph distance. The hyperplanes of $M$ are the equivalence classes of edges under the equivalence relation generated by identifying opposite edges of a four-cycle. Two distinct hyperplanes are transverse if a four-cycle has one pair of opposite edges in each class. The transversality graph $\mathcal T(M)$ has these hyperplanes as vertices, with adjacency precisely when they are transverse.

The supplied formulation describes the transversality degree of $G$ as the "minimum degree of a median graph whose transversality graph is isomorphic to $G$." The meaning of degree in this description is unresolved. For a finite nonempty graph $M$, write \[ \delta(M)=\min_{v\in V(M)}\deg_M(v),\qquad \Delta(M)=\max_{v\in V(M)}\deg_M(v). \] If finite realizing median graphs are intended, two different readings of the supplied description are \[ \min_{\substack{M\text{ finite median}\\\mathcal T(M)\cong G}}\delta(M) \qquad\text{and}\qquad \min_{\substack{M\text{ finite median}\\\mathcal T(M)\cong G}}\Delta(M). \] The first uses minimum vertex degree literally; the second minimizes maximum vertex degree over realizations. The supplied excerpt does not determine which reading defines $\operatorname{TD}(G)$. These expressions are stated only when the corresponding realization family is nonempty; no value for an empty family is supplied.

Problem, subject to these unresolved conventions. Determine how to compute $\operatorname{TD}(G)$. The supplied edited statement additionally asks for structural or computational complexity bounds for this invariant. A precise algorithmic formulation requires specification of the allowed input graphs, the allowed realizing median graphs, the meaning of their degree, and the treatment of inputs with no allowed realization. In particular, the supplied record does not state whether either graph must be finite. No choice among these missing conventions is asserted here.

Short English statement

The problem asks how to compute the smallest degree required of a median graph realizing a given graph as its transversality graph. The edited record also requests structural and complexity bounds. The degree convention and graph domains require clarification before this becomes a fully specified computational problem.

Sources

• Local registry: data/unsolvedmath/problems.json, supplied complete record for permanent UnsolvedMath ID $30006615$, source code catalogue entry, entitled Computing Transversality Degrees of Graphs. No individual proposer is supplied.
• Supplied report citation: Median Geometry and Applications (2026), Oberwolfach Reports, pp. 487--540, DOI 10.4171/owr/2026/8. Supplied source link: https://doi.org/10.4171/owr/2026/8.
• Supplied literature source, labelled "OWR report": https://ems.press/content/serial-article-files/53603. The supplied assessment identifies the target as Problem 6(ii), asking how to compute transversality degree.
• Literature assessment date: 2026-08-22. This is supplied dated curation, not independently verified. It labels the problem open, states that the report gives definitions and examples rather than an algorithm or classification, and reports that no resolution was found. The background explicitly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and says that only formula delimiters, notation, grammar, and typography were repaired, preserving mathematical content and scope. These are supplied editorial assertions, not independent verification in this draft.