Existence of Random-Graph Coloring Growth Rates

Definitions and mathematical statement

For a finite graph $G=(V,E)$ and an integer $k\geq 3$, define the number of proper colorings with labeled colors by \[ Z_k(G)=\#\left\{\sigma:V\to\{1,\ldots,k\}:\sigma(u)\neq\sigma(v)\text{ for every }\{u,v\}\in E\right\}. \] Under the usual simple-graph interpretation, $G(n,m)$ is uniformly distributed over the graphs on vertex set $\{1,\ldots,n\}$ having exactly $m$ edges. This model convention is not explicitly specified in the supplied record and requires confirmation.

The supplied displayed formulation asks whether, for every integer $k\geq3$ and every real $d>0$, the limit \[ \phi_k(d)=\lim_{n\to\infty}\left(\mathbb E\left[Z_k\left(G(n,m(n))\right)\right]\right)^{1/n} \] exists, where the expectation is over the random graph. The notation $\phi_k(d)$ makes explicit the dependence on $k$ suppressed in the supplied notation $\phi(d)$.

There are unresolved qualifications. In the simple-graph model, the average degree is $2m(n)/n$, so the conventional asymptotic interpretation would require integer edge counts satisfying \[ 0\leq m(n)\leq\binom n2,\qquad \frac{2m(n)}n\longrightarrow d. \] The record does not specify a rounding rule for $m(n)$, or whether the assertion is intended for every sequence satisfying this condition. These choices remain unresolved.

Moreover, the supplied original prose asks instead for existence of the expected $n$-th-root limit \[ \lim_{n\to\infty}\mathbb E\left[Z_k\left(G(n,m(n))\right)^{1/n}\right]. \] This differs from the displayed formulation, which takes the root after expectation. The supplied evidence does not resolve which is intended. Thus the formulas above record two candidate targets, rather than a single fully determined conjecture. The supplied record labels the problem open; that label is not independently verified here.

Short English statement

For each $k\geq3$ and positive average degree $d$, the problem asks whether a normalized coloring count of a random graph has a limit as its number of vertices grows. The supplied formulas disagree about whether expectation precedes the $n$-th root, and the edge-count sequence is unspecified. These issues require clarification before a unique precise statement can be fixed.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30002320$, source problem code catalogue entry, title Existence of Random-Graph Coloring Growth Rates, in the Oberwolfach Reports Open Problems collection. The record gives proposed year 2013 and names no proposer.
• Supplied report citation: Combinatorics and Probability (2014), Oberwolfach Reports, pp. 1087--1152, DOI 10.4171/owr/2013/18, https://doi.org/10.4171/owr/2013/18. The background describes these reports as documenting mathematical workshops and their open-problem discussions. The citation's 2014 designation and the record's 2013 year are retained as supplied.
• The registry assigns statement_status: corrected_verified and reports that the mathematical content was checked against the official report, with notation, context, and question form normalized without changing the source-level claim. This is supplied verification metadata, not an independent verification performed here; the root-placement discrepancy remains unresolved.
• Supplied literature source: Bapst--Coja-Oghlan--Hetterich--others, condensation transition, https://drops.dagstuhl.de/storage/00lipics/lipics-vol028-approx-random2014/LIPIcs.APPROX-RANDOM.2014.449/LIPIcs.APPROX-RANDOM.2014.449.pdf.
• Supplied literature source: Bayati--Gamarnik--Tetali, sparse random graphs, https://doi.org/10.1214/12-AOP816.
• Literature assessment dated exactly 2026-08-21: the supplied curation labels the problem open and states that existence of the normalized expected coloring-count limit for every $k$ at every positive density remains unresolved, while only a related free-energy limit is established. This is supplied dated curation derived from the OWR material, not independently verified. The supplied background expressly calls for independent verification of time-sensitive status and cited claims.