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$?
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$?
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$.)
Heckel [He24] and, independently, Steiner [St24b] have shown that it is not the case that $\chi(G)-\zeta(G)$ is bounded with high probability, and in fact if $\chi(G)-\zeta(G) \leq f(n)$ with high probability then $f(n)\geq n^{1/2-o(1)}$ along an infinite sequence of $n$. Heckel conjectures that, with high probability, \[\chi(G)-\zeta(G) \asymp \frac{n}{(\log n)^3}.\]
Determine $z(n)$ for small values of $z(n)$. In particular is it true that $z(12)=4$?
In fact there do exist such graphs - Bhavik Mehta found computationally that there is exactly one (up to taking the complement) graph on $12$ vertices such that both $G$ and its complement are $K_4$-free with chromatic number $\geq 5$. This graph was explicitly checked to have cochromatic number $4$, and hence this proves that indeed $z(12)=4$.
The values of $z(n)$ are now known for $1\leq n\leq 19$: \[1,1,2,2,3,3,3,3,4,4,4,4,5,5,5,6,6,6,6.\] (The only significant difficulty here is proving $z(12)=4$ - the others follow from easy inductive arguments and the facts that $R(3)=6$ and $R(4)=18$.) It is unknown whether $z(20)=6$ or $7$.
Gimbel [Gi86] has shown that $z(n) \asymp \frac{n}{\log n}$.
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)$.
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}?\]
The answer is yes, proved by Alon, Krivelevich, and Sudakov [AKS97].
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?
Is it true that if $G$ has no $K_5$ and $\zeta(G)\geq 4$ then $\chi(G) \leq \zeta(G)+2$?
This has been disproved by Steiner [St24b], who constructed a graph $G$ with $\omega(G)=4$, $\zeta(G)=4$, and $\chi(G)=7$.