19

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.

Jukka Suomela
  • 11,500
  • 2
  • 53
  • 116
Falk Hüffner
  • 1,023
  • 9
  • 13
  • 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 Oct 01 '10 at 11:01
  • If you are interested in a textbook with these types of colorings, look at http://www.amazon.com/Introduction-Hypergraph-Theory-Vitaly-Voloshin/dp/1606923722 If you are interested to learn more about applications of hypergraph coloring, have a look at the paper http://research.microsoft.com/en-us/um/people/moscitho/Publications/PODC_2012.pdf –  Aug 11 '13 at 16:10

4 Answers4

15

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

James King
  • 2,613
  • 18
  • 25
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.

Serge Gaspers
  • 5,116
  • 29
  • 42
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.

Jukka Suomela
  • 11,500
  • 2
  • 53
  • 116
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, 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.

András Salamon
  • 19,000
  • 3
  • 64
  • 150