VERIFIABLE
Open, but could be proved with a finite example.
Does there exist a $k>2$ such that the $k$-sized subsets of $\{1,\ldots,2k\}$ can be coloured with $k+1$ colours such that for every $A\subset \{1,\ldots,2k\}$ with $\lvert A\rvert=k+1$ all $k+1$ colours appear among the $k$-sized subsets of $A$?
A problem of Erdős and Rosenfeld. This is trivially possible for $k=2$. They were not sure about $k=6$.
This is equivalent to asking whether there exists $k>2$ such that the chromatic number of the
Johnson graph $J(2k,k)$ is $k+1$ (it is always at least $k+1$ and at most $2k$). The chromatic numbers listed at
this website show that this is false for $3\leq k\leq 8$.
View the LaTeX source
Additional thanks to: Bhavik Mehta
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 #835, https://www.erdosproblems.com/835, accessed 2025-11-16
