Erdős Problem #920 — Let fk(n)f_k(n) be the maximum possible chromatic number of a graph with nn vertices which contains no KkK_k.

About 57 years old · traced to

Let fk(n)f_k(n) be the maximum possible chromatic number of a graph with nn vertices which contains no KkK_k. Is it true that, for k≥4k\geq 4, fk(n)≫n1−1k−1(log⁡n)ckf_k(n) \gg \frac{n^{1-\frac{1}{k-1}}}{(\log n)^{c_k}} for some constant ck>0c_k>0?

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.