Problem 625

Erdős Problem #625: declared status 'open'. Formalized: no. The cochromatic number of $G$, denoted by $\zeta(G)$, is the minimum number of colours needed to colour the vertices of $G$ such that each colour class induces either a complete graph or empty graph. Let $\chi(G)$ denote the chromatic number. If $G$ is a random graph with $n$ vertices and each edge included independently with probability $1/2$ then is it true that almost surely$$\chi(G) - \zeta(G) \to \infty$$as $n\to \infty$? Current best: It is known that almost surely$$\frac{n}{2\log_2n}\leq \zeta(G)\leq \chi(G)\leq (1+o(1))\frac{n}{2\log_2n}.$$(The final upper bound is due to Bollob\'{a}s [Bo88]. Prize: $1000. Tags: chromatic number, graph theory.