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 statement2 of 3

A conjecture of Erdős, Gimbel, and Straight [EGS90], who proved that for every $n>2$ there exists some $f(n)$ such that if $G$ contains no clique on $n$ vertices then $\chi(G)\leq \zeta(G)+f(n)$ .

FormalConjectures/ErdosProblems/762.leanErdos762.erdos_762.variants.bounded_clique_number3 linesExact file

1∀ (n : ℕ),2  2 < n →3    ∃ f, ∀ (V : Type u_1) [Fintype V] (G : SimpleGraph V), G.CliqueFree n → G.chromaticNumber ≤ G.cochromaticNumber + ↑f

SolvedStatement only, no proof

Sources

Search problems.science