Problem 1104

Erdős Problem #1104: declared status 'open'. Formalized: yes. Let $f(n)$ be the maximum possible chromatic number of a triangle-free graph on $n$ vertices. Estimate $f(n)$. Current best: The best bounds available are$$(1-o(1))(n/\log n)^{1/2}\leq f(n) \leq (2+o(1))(n/\log n)^{1/2}.$$The upper bound is due to Davies and Illingworth [DaIl22], the lower bound follows from a construction of Hefty, Horn, King, and Pfender [HHKP25]. Prize: no. OEIS: A292528. Tags: chromatic number, graph theory.