Erdős Problem 1092

Let $f_r(n)$ be maximal such that, if a graph $G$ has the property that every subgraph $H$ on $m$ vertices is the union of a graph with chromatic number $r$ and a graph with $\leq f_r(m)$ edges, then $G$ has chromatic number $\leq r+1$.

Erdős asked whether:

• f 2 n ≫ n
• more generally, f r n ≫ r * n

This problem is currently open.

Reference: https://www.erdosproblems.com/1092

noncomputable def Erdos1092.f (r n : ℕ) : ℕ

$f_r(n)$ is maximal such that, if a graph $G$ on $n$ vertices has the property that every subgraph $H$ on $m$ vertices has chromatic number $\leq r+1$ once we remove $f_r(m)$ edges from it.

Equations

• One or more equations did not get rendered due to their size.

theorem Erdos1092.f_asymptotic_2 : sorry ↔ (fun (n : ℕ) => ↑n) =o[Filter.atTop] fun (n : ℕ) => ↑(f 2 n)

theorem Erdos1092.f_asymptotic_general : sorry ↔ ∀ (r : ℕ), (fun (n : ℕ) => ↑r * ↑n) =o[Filter.atTop] fun (n : ℕ) => ↑(f r n)