Erdős Problems
Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated

Problem 1104

../

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

Status. Open.

Source. erdosproblems.com/1104, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #1104, https://www.erdosproblems.com/1104.

References.

  • [DaIl22] Davies, Ewan and Illingworth, Freddie, The χ\chi-Ramsey problem for triangle-free graphs. SIAM J. Discrete Math. (2022), 1124-1134.
  • [HHKP25] Z. Hefty, P. Horn, D. King, and F. Pfender, Improving R(3,k)R(3,k) in just two bites. arXiv:2510.19718 (2025).
  • [Ki95] Kim, J. H., The Ramsey number R(3,t)R(3,t) has order of magnitude $t^2/\log t$. Random Structures and Algorithms (1995), 173-207.

Formalization. Statement in formal-conjectures.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (9)
Problem 1011Problem 920Graph ColoringGraph Coloringgraph_coloring/davies_2022_ramsey_problem_triangle_free_graphsTheorem 1 (p. 3): a triangle-free graph on n vertices has chromatic number at most (2+o(1))√(n/log n)ramsey_theory/hefty_2025_improving_just_two_bitesTheorem 1.3 (p. 2): triangle-free graphs on n vertices with independence number below (1+ε)√(n log n)ramsey_theory/kim_1995_ramsey_number_has_order_magnitude
Graph