Erdős problem 762
The cochromatic number of , denoted by , is the minimum number of colours needed to colour the vertices of such that each colour class induces either a complete graph or empty graph.
Sources
FormalConjectures/ErdosProblems/
762.lean
Retained formal statement
The cochromatic number of , denoted by , is the minimum number of colours needed to colour the vertices of such that each colour class induces either a complete graph or empty graph.
Is it true that if has no and then ?
This has been disproved by Steiner [St24b], who constructed a graph with , , and .
False ↔ ∀ (V : Type u_1) [Fintype V] (G : SimpleGraph V), G.CliqueFree 5 → 4 ≤ G.cochromaticNumber → G.chromaticNumber ≤ G.cochromaticNumber + 2