← All problems

Erdős Problem #1104 — Chromatic Ramsey growth of triangle-free graphs

59 years old · traced to

For each positive integer nn, let GG range over finite triangle-free graphs with exactly nn vertices, where triangle-free means that GG contains no cycle of length 33. Write χ(G)\chi(G) for the least number of colors in a proper vertex coloring, and define

f(n)=max⁡∣V(G)∣=n, G triangle-freeχ(G).f(n)=\max_{|V(G)|=n,\,G\text{ triangle-free}}\chi(G).

Estimate the asymptotic growth of f(n)f(n) as n→∞n\to\infty. 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 GG satisfies α(G)χ(G)≥∣V(G)∣\alpha(G)\chi(G)\ge |V(G)|, where α(G)\alpha(G) is its largest independent-set size. The independence-number bound of Ajtai, Komlós, and Szemerédi therefore gives an initial upper bound on f(n)f(n); 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

Progress summary

Never refreshed

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.