Skip to content

Erdős problem 762

The cochromatic number of GG, denoted by ζ(G)\zeta(G), is the minimum number of colours needed to colour the vertices of GG 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 statement1 of 3

The cochromatic number of GG, denoted by ζ(G)\zeta(G), is the minimum number of colours needed to colour the vertices of GG such that each colour class induces either a complete graph or empty graph.

Is it true that if GG has no K5K_5 and ζ(G)4\zeta(G)\geq 4 then χ(G)ζ(G)+2\chi(G) \leq \zeta(G)+2?

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

FormalConjectures/ErdosProblems/762.leanErdos762.erdos_7623 linesExact file
False  ∀ (V : Type u_1) [Fintype V] (G : SimpleGraph V),    G.CliqueFree 5 → 4 ≤ G.cochromaticNumberG.chromaticNumberG.cochromaticNumber + 2
SolvedProof has a holelean4external proof

The proof uses `sorry`: part of the argument is written but not proved. Lean accepts the file; it does not accept the theorem.

Search problems.science

Find a Problem, Result, source, or page