S. Petkov

A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph

Let $\zeta(G)$ denote the minimum number of parts in a partition of $V(G)$ in which every part induces either a clique or an independent set. Erd\H{o}s and Gimbel asked whether, for $G_n\sim G(n,1/2)$, the difference $\chi(G_n)-\zeta(G_n)$ tends to infinity with high probability. We resolve this problem along the full...