Problem 762

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

Source: erdosproblems.com/762

Graph theory
Chromatic number

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

DISPROVED (LEAN). The site prints the label DISPROVED (LEAN); the Lean proofs the label refers to are third-party files, linked from the claim page below, which this corpus has not built.

EGS90: Erdős, Paul and Gimbel, John and Straight, H. Joseph, Chromatic number versus cochromatic number in graphs with bounded clique number. European J. Combin. (1990), 235-240.
St24b: R. Steiner, On the difference between the chromatic and cochromatic number. arXiv:2408.02400 (2024). Published as R. Steiner, On the Difference Between the Chromatic and Cochromatic Number, SIAM J. Discrete Math. 39 (2025), no. 4, 2268–2274, doi:10.1137/24M1715180.

Problem 762

Status

Proof claims

Discussion