# "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].

It is also at most as hard as $k$-coloring a graph $G=(X,E)$, where $E$ is formed by making each $X_i$ into a clique. Your restriction that all $X_i$ are of size $k$ means that you can cover each edge of $G$ with a clique on $k$ vertices.

• Indeed. This looks like a transformation of Covering By Cliques in Garey/Johnson. NP-complete for fixed $k \ge 3$, but has a polynomial time algorithm for $k \le 2$ (as Falk mentions). Aug 20 '10 at 16:21
• The construction of $G$ suggested here is precisely the Gaifman graph. Aug 20 '10 at 23:26
• That's right. $G$ is indeed the Gaifman graph. Aug 21 '10 at 10:31

At least as hard as $k$-colouring an arbitrary graph $G = (V,E)$. For each edge $e = \{u,v\}$ you have a subset $X_e = \{ u, v, x(e,3), x(e,4), \dotsc, x(e,k) \}$; here each $x(e,j)$ is a dummy element that is not present in any other subset. If you can $k$-colour $G$, you can easily find a colouring of the set system (just colour the dummy elements greedily), and vice versa.

A colouring in which every hyperedge is polychromatic (or rainbow) is also known as a strong colouring.

Note that a strong colouring of a hypergraph is precisely a proper colouring of the Gaifman graph of the hypergraph. (The Gaifman graph (or primal graph or 2-section) of a hypergraph is formed by adding edges between any two vertices that appear together in some hyperedge.)

So if you are looking for a $k$-colouring of an $r$-uniform hypergraph $H$, then you can equivalently look for a $k$-colouring of the Gaifman graph of $H$. The case $r=2$ corresponds to graph colouring, which is polynomial-time for $k=2$ and NP-complete for $k\ge 3$. Obviously $r <2$ is trivial, $k\lt r$ leads to no solutions, and the other cases are all NP-complete.

A useful reference which has most of the above definitions is Vitaly I. Voloshin, Coloring Mixed Hypergraphs: Theory, Algorithms and Applications, Fields Institute Monographs 17, AMS, 2002, ISBN 0-8218-2812-6. This book covers the more general case of weak colourings, with particular focus on combining two types of coloured edges: $C$-edges, which have at least two vertices with a common colour, and $D$-edges, which have at least two vertices of different colours.

• What would you recommend as a citation for the NP-hardness of the problem? The above book? Jun 19 '16 at 21:12
• @domotorp no, the book focuses on weak colouring. See the answer by Jukka. Jun 21 '16 at 10:22