Erdős Problem #920 — Chromatic lower bounds for -free graphs
For integers and , let be the maximum chromatic number among finite simple graphs with exactly vertices that contain no clique of order (that is, no subgraph isomorphic to ): Erdős Problem #920
The question is whether, for every fixed integer , there are constants such that for all sufficiently large integers , Erdős Problem #920
Here and may depend on ; the exponent is the constant denoted in the original question. Erdős Problem #920
Background
This extremal function asks how large chromatic complexity can remain when a fixed clique is forbidden. The problem is attributed to Erdős [Er69b]. Graver and Yackel established the upper bound, for fixed , Erdős Problem #920 Graver and Yackel (1968)
Erdős Problem #920 Graver and Yackel (1968)
Thus the question seeks a lower bound close in its power of to this known upper bound, allowing a power of a logarithm. Erdős Problem #920 Graver and Yackel (1968)
Off-diagonal Ramsey bounds provide a route to lower bounds for . In the case , a graph on vertices with no and independence number less than has chromatic number at least . Mattheus and Verstraete's lower bound for supplies graphs of this kind at the scale needed for the bound stated below. Erdős Problem #920 Some recent results in Ramsey theory
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.