Erdős problem 762 · problems.science

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

Browse retained paths and inspect the exact material available for this Problem.

3 retained statements2415f78e850a

Open selected source

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

Sources

Search problems.science