Status
On this page
Status
Topics
Status
On this page
Status
Topics
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 surely
as ?
Source: erdosproblems.com/625
An accepted solution exists. The statement is true.
SOLVED, the site's label since 5 September 2026, when the curator changed it from OPEN and credited Petkov and GPT-5.6 in the commentary (the page was last edited that day). The site's commentary records the known bounds , the results of Heckel and Steiner that the gap is not bounded with high probability, Heckel's conjecture that it is of order , Heckel's bound for roughly of all , and, since September 2026, an improvement by Petkov and GPT-5.6, through the proof claims, to a gap almost surely, as Heckel predicted. Two full proof claims are recorded: Petkov's manuscript (forum 14 July 2026, arXiv 31 August 2026), whose uniform main theorem gives an explicit lower bound with probability tending to one along all integers and carries an external kernel-verification record the corpus did not build, and Serraj's manuscript (9 September 2026), a different route. Neither is refereed. Petkov's is accepted on the curator's label and credit. Serraj's, which the site does not credit, is pending. The problem therefore stands solved and proved. The assessment below records what each source states and what the corpus's reviews cover.