"All-different hypergraph coloring" - known problem? I am interested in the following problem: Given a set X and subsets X_1, ..., X_n of X, find a coloring of the elements of X with k colors such that the elements in each X_i are all differently colored. More specifically, I am looking at the case where all X_i are of size k. Is this known in the literature under some name?  I am looking for characterizations of colorable instances and results on complexity (P vs. NP-hard). For example, for k=2, colorable instances correspond to bipartite graphs, and thus the problem can be solved in polynomial time.
I believe this is known in the literature as the problem of finding a strong k-coloring for a k-uniform hypergraph.  This should be a good place to start: [PDF].