<p>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.</p>

CC BY-SA 2.5
2010-08-20T15:01:21.027Z
2010-08-20T15:01:21.027Z
Jukka Suomela
<p>A colouring in which every hyperedge is <em>polychromatic</em> (or <em>rainbow</em>) is also known as a <em>strong colouring</em>.</p>

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

<p>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 &lt;2$ is trivial, $k\lt r$ leads to no solutions, and the other cases are all NP-complete.</p>

<p>A useful reference which has most of the above definitions
is Vitaly I. Voloshin, <a href="http://bookstore.ams.org/fim-17" rel="nofollow"><em>Coloring Mixed Hypergraphs: Theory, Algorithms and Applications</em></a>, Fields Institute Monographs <strong>17</strong>, 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.</p>

CC BY-SA 3.0
2016-06-19T21:12:50.537Z
What would you recommend as a citation for the NP-hardness of the problem? The above book?
domotorp
CC BY-SA 3.0
2016-06-21T10:22:13.227Z
@domotorp no, the book focuses on weak colouring.  See the answer by Jukka.
András Salamon
CC BY-SA 3.0
2010-08-20T17:23:01.750Z
2016-02-20T10:35:34.470Z
2016-02-20T10:35:34.470Z
András Salamon
<p>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.</p>

CC BY-SA 2.5
2010-08-20T16:21:20.170Z
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).
Daniel Apon
CC BY-SA 2.5
2010-08-20T23:26:31.900Z
The construction of $G$ suggested here is precisely the Gaifman graph.
András Salamon
CC BY-SA 2.5
2010-08-21T10:31:01.473Z
That's right. $G$ is indeed the Gaifman graph.
Serge Gaspers
CC BY-SA 2.5
2010-08-20T15:48:20.800Z
2010-08-20T15:48:20.800Z
Serge Gaspers
<p>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: <a href="http://www.hr.is/faculty/mmh/papers/strongcol.pdf">[PDF]</a>.</p>

CC BY-SA 2.5
2010-08-20T16:15:11.613Z
2010-08-20T16:15:11.613Z
James King
<p>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.</p>

CC BY-SA 2.5
2010-10-01T11:01:30.113Z
If the hypergraph has bounded degree D, the max # of colours that are usable is Theta(D/log k): see http://arxiv.org/abs/1009.5893 or http://arxiv.org/abs/1009.6144
daveagp
<cc.complexity-theory><reference-request><np-hardness><hypergraphs>
"All-different hypergraph coloring" - known problem?
Falk Hüffner
# "All-different hypergraph coloring" - known problem?

(Asked by: username_0 on 2010-08-20)

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.

**Tags:** cc.complexity-theory, reference-request, np-hardness, hypergraphs

> **Comments:**
> **username_1**: If the hypergraph has bounded degree D, the max # of colours that are usable is Theta(D/log k): see http://arxiv.org/abs/1009.5893 or http://arxiv.org/abs/1009.6144  

---

## 4 answers

### Answer by username_7 on 2010-08-20. Score: 15 | Accepted answer

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]](http://www.hr.is/faculty/mmh/papers/strongcol.pdf).


---

### Answer by username_5 on 2010-08-20. Score: 10

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.

> **Comments:**
> **username_6**: 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).  
> **username_3**: The construction of $G$ suggested here is precisely the Gaifman graph.  
> **username_5**: That's right. $G$ is indeed the Gaifman graph.  

---

### Answer by username_2 on 2010-08-20. Score: 8

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.


---

### Answer by username_3 on 2010-08-20. Score: 8

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*](http://bookstore.ams.org/fim-17), 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.

> **Comments:**
> **username_4**: What would you recommend as a citation for the NP-hardness of the problem? The above book?  
> **username_3**: @username_4 no, the book focuses on weak colouring.  See the answer by Jukka.  

---

