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$?

OPEN - $1000

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$?

A problem of Erdős and Gimbel (see also [Gi16]). At a conference on random graphs in Poznan, Poland (most likely in 1989) Erdős offered \$100 for a proof that this is true, and \$1000 for a proof that this is false (although later told Gimbel that \$1000 was perhaps too much).

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ás [Bo88]. The first inequality follows from the fact that almost surely $G$ has clique number and independence number $< 2\log_2n$.)

OPEN

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 $z(n)$ be the maximum value of $\zeta(G)$ over all graphs $G$ with $n$ vertices.

Determine $z(n)$ for small values of $z(n)$. In particular is it true that $z(12)=4$?

A question of Erdős and Gimbel, who knew that $4\leq z(12)\leq 5$ and $5\leq z(15)\leq 6$. To determine whether $z(12)=4$ is asking whether there is a graph $G$ on $12$ vertices such that both $G$ and its complement are $K_4$-free, but both $G$ and its complement have chromatic number $5$.

Gimbel [Gi86] has shown that $z(n) \asymp \frac{n}{\log n}$.

OPEN

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 $z(S_n)$ be the maximum value of $\zeta(G)$ over all graphs $G$ which can be embedded on $S_n$, the orientable surface of genus $n$. Determine the growth rate of $z(S_n)$.

A problem of Erdős and Gimbel. Gimbel [Gi86] proved that
\[\frac{\sqrt{n}}{\log n}\ll z(S_n) \ll \sqrt{n}.\]

SOLVED

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.

If $G$ is a graph with chromatic number $\chi(G)=m$ then must $G$ contain a subgraph $H$ with \[\zeta(H) \gg \frac{m}{\log m}?\]

A problem of Erdős and Gimbel, who proved that there must exist a subgraph $H$ with
\[\zeta(H) \gg \left(\frac{m}{\log m}\right)^{1/2}.\]
The proposed bound would be best possible, as shown by taking $G$ to be a complete graph.

The answer is yes, proved by Alon, Krivelevich, and Sudakov [AKS97].

OPEN

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. The dichromatic number of $G$, denoted by $\delta(G)$, is the minimum number $k$ of colours required such that, in any orientation of the edges of $G$, there is a $k$-colouring of the vertices of $G$ such that there are no monochromatic oriented cycles.

Must a graph with large chromatic number have large dichromatic number? Must a graph with large cochromatic number contain a graph with large dichromatic number?

The first question is due to Erdős and Neumann-Lara. The second question is due to Erdős and Gimbel. A positive answer to the second question implies a positive answer to the first via the bound mentioned in [760].

OPEN

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.

Is it true that if $G$ has no $K_5$ and $\zeta(G)\geq 4$ then $\chi(G) \leq \zeta(G)+2$?

A conjecture of Erdős, Gimbel, and Straight [EGS90].