Structural Characterization of Exceptional Borel Graphs

Definitions and mathematical statement

Under the usual simple undirected graph convention, a Borel graph is a pair $G=(X,E)$, where $X$ is a standard Borel space and $E\subseteq X\times X$ is Borel, symmetric, and irreflexive. A standard Borel space is a measurable space isomorphic to a Borel subset of a Polish space. These graph conventions are not explicitly specified in the supplied excerpt and require confirmation against its omitted context.

For a positive integer $k$, a Borel proper $k$-coloring of $G$ is a Borel map $c:X\to\{1,\ldots,k\}$, with the finite target given its discrete Borel structure, such that \[ \forall x,y\in X,\qquad (x,y)\in E\ \Longrightarrow\ c(x)\ne c(y). \] The notation $\chi_B(G)\le k$ means that such a coloring exists. Define \[ \mathcal C_k=\{G:G\text{ is a Borel graph and }\chi_B(G)\le k\}. \]

Requested characterization. The source asks for a reasonable structural characterization of Borel graphs for which certain preceding general results fail, and asks whether an analogous characterization exists for $\mathcal C_k$, for each fixed $k\in\mathbb N$.

Unresolved qualifications. The supplied excerpt does not identify the preceding general results, the proposed generalization, or what their failure means. Consequently, the exceptional class in the first question cannot be defined precisely from this record. The finite-coloring class above has a precise meaning under the stated conventions, but the source does not specify what counts as a reasonable structural characterization or what makes it analogous to the first characterization. Thus the second question remains a request for necessary and sufficient structural criteria, with the permitted form of those criteria unresolved. The source also leaves the convention for $\mathbb N$ unspecified; the definition above covers positive $k$. If zero is intended, a coloring into the empty color set exists exactly when $X=\varnothing$.

Short English statement

The source asks which structural features explain the failure of unspecified general results for Borel graphs, and whether similar criteria characterize graphs admitting a Borel proper coloring with at most a fixed $k$ colors. The omitted antecedents prevent a precise formulation of the first target class; the intended kind of structural criterion also remains unspecified.

Sources

• Local UnsolvedMath registry, supplied complete source record: permanent ID $30006514$, title Structural Characterization of Exceptional Borel Graphs, exact source problem code catalogue entry. No individual proposer is supplied.
• Supplied report citation: Homogeneous Structures: Model Theory meets Universal Algebra (2026), Oberwolfach Reports, DOI 10.4171/owr/2025/58, pp. 3063--3124. The original excerpt identifies p. 3081. https://doi.org/10.4171/owr/2025/58. The record gives proposed year 2025; its citation year is 2026. These supplied dates are retained without resolving their relationship.
• Supplied literature reference: Todorčević--Vidnyánszky, A complexity problem for Borel graphs. https://link.springer.com/article/10.1007/s00222-021-01047-z.
• Supplied literature reference: Brandt et al., On Homomorphism Graphs. https://arxiv.org/abs/2111.03683.
• Literature assessment dated exactly 2026-08-22: supplied dated curation, not independently verified here. The record labels the problem partially_solved and states that the "Gowers--Kechris dichotomy" handles the basic uncountable-chromatic case, that later work gives complexity results for fixed finite bounds, and that no general structural characterization is known. The supplied background describes this as dated literature triage derived from OWR curation and requests independent verification of time-sensitive status and cited claims. The theorem name, its applicability, and these literature conclusions are recorded as supplied claims.
• The registry assigns statement status corrected_verified and reports that the official report was checked, the mathematical question isolated from surrounding exposition, and its notation repaired. This is a supplied source-verification claim, not an independent verification performed for this draft.