Problem Statement
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$?
Categories:
Graph Theory Hypergraphs
Progress
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$.
Source: erdosproblems.com/835 | Last verified: January 16, 2026