Chromatic Numbers of Exchangeable Graphon Random Graphs

Definitions and mathematical statement

For terminology, let $(\Omega,\mathcal A,\mu)$ be a probability space. A graphon is a symmetric measurable function $W:\Omega^2\to[0,1]$. For an integer $n\geq1$, the associated random simple graph $G(n,W)$ has vertex set $\{1,\ldots,n\}$: sample independent points $X_1,\ldots,X_n$ with law $\mu$, and, conditional on these points, include each edge $\{i,j\}$, $i<j$, independently with probability $W(X_i,X_j)$. Its distribution is invariant under permutations of the vertex labels. These are standard definitions supplied for context; the excerpt does not specify its underlying probability space or additional hypotheses on $W$.

For a finite nonempty simple graph $G$, its chromatic number is \[ \chi(G)=\min\left\{k\geq1:\text{there exists }c:V(G)\to\{1,\ldots,k\}\text{ with }c(u)\neq c(v)\text{ for every }\{u,v\}\in E(G)\right\}. \] A block graphon is constant almost everywhere on each product $A_i\times A_j$ of cells of a finite measurable partition of $\Omega$. For graphons represented on the same probability space, approximation in $L^\infty$ means \[ \|W_m-W\|_{L^\infty(\mu\otimes\mu)} =\operatorname*{ess\,sup}_{(x,y)\in\Omega^2}|W_m(x,y)-W(x,y)|\longrightarrow0. \]

Status of the mathematical statement. The supplied passage describes an asymptotic conjecture for $\chi(G(n,W))$, attributed to Martinsson, Panagiotou, Su, and Trujić, extending Bollobás' classical result for the binomial random graph. It reports confirmation for block graphons and for a special class of graphons approximable by block graphons in $L^\infty$, and reports the conjectured upper bound for general graphons. These are supplied descriptions of results, not independently verified assertions in this draft. The special class is not specified; the passage does not assert that every graphon admitting such approximation belongs to it.

Unresolved formulation. No precise general conjecture can be recovered from this record. The excerpt gives neither the proposed asymptotic expression nor its normalization, mode of convergence, full graphon hypotheses, or definitions of any governing quantities. Accordingly, no universally quantified asymptotic formula or lower bound is asserted here. The supplied registry marks this statement as unrecoverable, explains that it summarizes proved results rather than stating the complete conjecture, and places the concrete convergence question in the separate record OWR-12697712-004. That separate record is not supplied and is not reconstructed here.

Short English statement

The source summarizes progress on a conjectured asymptotic chromatic number for random graphs generated by graphons. It reports results for block graphons, a special approximable class, and an upper bound for general graphons. The actual conjectural formula and its hypotheses are missing, so this permanent record supports a provenance-preserving statement of the formulation gap, requiring human mathematical review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30005484$, title Chromatic Numbers of Exchangeable Graphon Random Graphs, exact source code catalogue entry, in the Oberwolfach Reports Open Problems collection. The supplied proposed year is 2023; no proposer is identified. Its status label is partially_solved, while its statement status is unrecoverable. These are supplied registry labels, not independently verified mathematical conclusions.
• Random Graphs: Combinatorics, Complex Networks and Disordered Systems (2023), Oberwolfach Reports, pp. 883--914, DOI 10.4171/owr/2023/16. Supplied source link: https://doi.org/10.4171/owr/2023/16. The record describes the passage as retained verbatim from workshop-report context.
• Supplied literature source: Graphon chromatic polynomials, https://arxiv.org/abs/2109.07773.
• Supplied literature source: OWR 2023 report, https://ems.press/content/serial-article-files/47010?nt=1.
• The literature assessment dated exactly 2026-08-22 is supplied dated curation, not independently verified. It labels the problem partially solved and states that the cited work extends the chromatic polynomial expectation to block graphons and gives upper bounds for general graphons, while the full general statement is not proved. The background explicitly calls this dated literature triage derived from supplied OWR curation and requests independent verification of time-sensitive status and cited claims.
• The excerpt attributes the asymptotic conjecture to Martinsson, Panagiotou, Su, and Trujić, and refers to Bollobás' classical result. It says the talk is based on references [1] and [2], whose bibliographic entries are not supplied. The report citation supplies provenance, but no complete authoritative statement of the general conjecture is included.