erdős #625
The cochromatic number of , denoted by , is the minimum number of colours needed to colour the vertices of such that each colour class induces either a complete graph or empty graph. Let denote the chromatic number.If is a random graph with vertices and each edge included independently with probability then is it true that almost surelyas ?
Worked, still open.
graph theory · open · prize $1000 · 0 attempts
use this record
vela registry pull vfr_37aec80d874a0239vela reproduce examples/erdos-problemsevidence
unverified AI candidates (2)
gpt-erdos · GPT-5.2 Pro + Deep Research · unverified
For (G\sim G_{n,1/2}) one has [ \chi(G)\sim \frac{n}{2\log_2 n} \qquad\text{and}\qquad \zeta(G)\sim \frac{n}{2\log_2 n} ] with high probability [[nomath]](so $\chi/\zeta\to 1$)[[/nomath]].
candidate solution ↗llm-hunter · gpt pro 5.2 · unverified
1 LLM attack(s) recorded (gpt pro 5.2); unverified.
candidate solution ↗links
Create a formalisation here · link
status
open