Erdős 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.

Sources

The source's own material, retained exactly.

3 retained statements36c6d0fef71a

FormalConjectures/ErdosProblems/

762.lean

Retained formal statement3 of 3

This has been disproved by Steiner [St24b], who constructed a graph $G$ with $\omega(G)=4$ , $\zeta(G)=4$ , and $\chi(G)=7$ .

FormalConjectures/ErdosProblems/762.leanErdos762.erdos_762.variants.steiner1 lineExact file

1∃ n G, G.cliqueNum = 4 ∧ G.cochromaticNumber = 4 ∧ G.chromaticNumber = 7

SolvedStatement only, no proof