Let $f (n)$ be the maximum possible chromatic number of a triangle-free graph on $n$ vertices. Estimate $f (n)$ .

Worked, still open.

graph theory · open · formalized (Lean) · 0 attempts

use this record

vela registry pull vfr_37aec80d874a0239

vela reproduce examples/erdos-problems

evidence

unverified AI candidates (2)

gpt-erdos · GPT-5.2 Pro + Deep Research · unverified

[ f(n)=\max{\chi(G): |V(G)|=n,; G\text{ triangle-free}}. ]

candidate solution ↗

llm-hunter · gpt pro 5.2 · unverified

1 LLM attack(s) recorded (gpt pro 5.2); unverified.

candidate solution ↗

formal

AMS 5 · solved (literature)

theorem erdos_1104.variants.lower :
    ∃ c₁ : ℝ, 0 < c₁ ∧ c₁ ≤ 1 ∧
      (∀ᶠ n : ℕ in atTop,
        c₁ * Real.sqrt (n : ℝ) / Real.sqrt (Real.log (n : ℝ))
          ≤ (triangleFreeMaxChromatic n : ℝ))

formal-conjectures/1104.lean ↗

oeis

A292528 — Minimal number of vertices in a triangle-free graph with chromatic number n.1,2,5,11,22

links

#1013Let

h_{3} (k)

be the minimal

n

such that there exists a triangle-free graph on

n

vertices with chromatic number

k

. Find an asymptotic for

h_{3} (k)

, and also prove

k \to \infty lim \frac{h _{3} ( k + 1 )}{h _{3} ( k )} = 1.

A292528

status