A graph G is said to be uniquely colorable it has only one optimal coloring up to permutation of the colors

Definitions and mathematical statement

For a finite simple graph $G$, let $\chi(G)$ be the least number of independent sets partitioning its vertex set. Define $\mathcal P(G)$ as the set of unordered partitions into exactly $\chi(G)$ nonempty independent sets. The graph is uniquely colorable when $|\mathcal P(G)|=1$. This identifies color-label permutations only; vertices remain distinct.

Let $G_n\sim G(n,1/2)$: each unordered pair in the labeled vertex set $\{1,\ldots,n\}$ is independently an edge with probability $1/2$. "Asymptotically almost surely" means with probability tending to $1$ as $n\to\infty$. The source asks, "Is it false that $G(n,1/2)$ is uniquely colorable (aas)?" The assertion it asks to negate is \[ \Pr\{|\mathcal P(G_n)|=1\}\longrightarrow1. \] Its logical negation is weaker than the natural stronger alternative \[ \Pr\{|\mathcal P(G_n)|\ge2\}\longrightarrow1. \] The excerpt does not state which negative asymptotic conclusion is intended, so these are not silently equated.

The supplied OPEN-TRIAGE summary adopts the stronger nonuniqueness reading and calls it effectively known, asserting many or exponentially many optimal colorings. It invokes the approximate chromatic-number scale $n/(2\log_2n)$, Achlioptas--Naor, and vague concentration language, but supplies no precise multiplicity theorem or exponential scale. Chromatic-number asymptotics alone do not specify the number of optimal partitions. Thus those comments are retained as unverified supplied assessments, not a rigorous resolution of either displayed limit. The registry itself remains open.

Short English statement

Are dense random graphs asymptotically uniquely optimally colorable, or do they have multiple optimal partitions with probability tending to one? The source's negated wording and its uncited multiplicity assessment need review.

Sources

• Local UnsolvedMath registry, permanent ID $3100026$, exact source code catalogue entry, "A graph G is said to be uniquely colorable it has only one optimal coloring up to permutation of the colors."
• Cooper, Combinatorial Problems I Like, October 2020 snapshot, Graphs, Hypergraphs, Set Systems, Designs, source-order bullet 26; https://people.math.sc.edu/cooper/combprob.html. HTML extraction; recorded access 2026-07-29.
• Supplied research summary names Achlioptas--Naor and random-graph coloring theory without a complete citation or a precise optimal-coloring multiplicity result.