Erdős Problem #924 - Discussion thread

Let $k\geq 2$ and $l\geq 3$. Is there a graph $G$ which contains no $K_{l+1}$ such that every $k$-colouring of the edges of $G$ contains a monochromatic copy of $K_l$?

#924: [Er69b][Er75b]

graph theory | ramsey theory

A question of Erdős and Hajnal. Folkman [Fo70] proved this when $k=2$. The case for general $k$ was proved by Nešetřil and Rödl [NeRo76].

See [582] for a special case and [966] for an arithmetic analogue.

View the LaTeX source

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)

When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:

T. F. Bloom, Erdős Problem #924, https://www.erdosproblems.com/924, accessed 2025-11-16

0 comments on this problem

Order by oldest first or newest first.

All comments are the responsibility of the user. Comments appearing on this page are not verified for correctness. Please keep posts mathematical and on topic.

Back to the forum