Erdős Problem #1104 — Chromatic Ramsey growth of triangle-free graphs
For each positive integer , let range over finite triangle-free graphs with exactly vertices, where triangle-free means that contains no cycle of length . Write for the least number of colors in a proper vertex coloring, and define
Estimate the asymptotic growth of as . Erdős Problem #1104 The χ-Ramsey problem for triangle-free graphs
Background
Erdős posed this question in 1967, asking how large the chromatic number of a triangle-free graph can be in terms of its number of vertices (and also its number of edges). The problem is related to the classical Ramsey question of how large an independent set must be in a triangle-free graph: every graph satisfies , where is its largest independent-set size. The independence-number bound of Ajtai, Komlós, and Szemerédi therefore gives an initial upper bound on ; repeatedly removing large independent sets and assigning each a new color yields the corresponding coloring bound. The χ-Ramsey problem for triangle-free graphs
The sharper constant in the early upper bound came from Shearer’s improvement to the triangle-free independence-number estimate, together with an observation of Erdős and Hajnal that converts such estimates into coloring bounds. On the construction side, Kim’s probabilistic construction and later analysis of the triangle-free process produced graphs with large chromatic number. These developments brought the upper and lower bounds to the same order of growth, while leaving a gap in their leading constants. The χ-Ramsey problem for triangle-free graphs
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.