Problem Statement
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$?
Is it true that if $G$ has no $K_5$ and $\zeta(G)\geq 4$ then $\chi(G) \leq \zeta(G)+2$?
Categories:
Graph Theory Chromatic Number
Progress
A conjecture of Erdős, Gimbel, and Straight [EGS90], who proved that for every $n>2$ there exists some $f(n)$ such that if $G$ contains no clique on $n$ vertices then $\chi(G)\leq \zeta(G)+f(n)$.This has been disproved by Steiner [St24b], who constructed a graph $G$ with $\omega(G)=4$, $\zeta(G)=4$, and $\chi(G)=7$.
Source: erdosproblems.com/762 | Last verified: January 16, 2026