Graph colouring problems are, already, hard enough for most people. Even so, I'm going to have to be difficult and ask a problem about hypergraph colouring.
What efficient algorithms are there for finding an approximately-optimal edge-colouring for k-uniform hypergraphs?
A k-uniform hypergraph is one in which each edge contains precisely k vertices; the usual case of a simple graph is k=2. More precisely, I'm interested in labelled k-uniform hypergraphs, in which two edges may actually have the same vertex-set; but I'll settle for something on k-regular hypergraphs with edges intersecting at no more than k−1 vertices.
An edge-colouring of hypergraphs is one in which edges of the same colour do not intersect, as with the case of graphs. The chromatic index χ'(H) is the minumum number of colours required, as usual.
I would like results on deterministic or randomized polynomial time algorithms.
I'm looking for the best known approximation-factor/additive-gap between what can be efficiently found, and the actual chromatic index χ'(H) --- or for that matter, the best efficiently-attainable result in terms of parameters such as the maximum vertex degree Δ(H), the size of the hypergraph, etc.
Edit: prompted by Suresh's remarks about hypergraph duals below, I should note that this problem is equivalent to the problem of finding a strong vertex colouring of a k-regular hypergraph: that is, where each vertex belongs to k distinct edges [but the edges may now contain differing numbers of vertices], and we want a vertex colouring such that any two adjacent vertices have different colours. This reformulation also does not seem to have an obvious solution.
In the case of graphs, Vizing's Theorem not only guarantees that the edge-chromatic number for a graph G is either Δ(G) or Δ(G)+1, standard proofs of it also give an efficient algorithm for finding a Δ(G)+1-edge-colouring. This result would be good enough for me if I were interested in the case k=2; however, I'm specifically interested in k>2 arbitrary.
There doesn't seem to be any well-known results about bounds on hypergraph-edge-colouring, unless you add restrictions such as every edge intersecting in at most t vertices. But I don't need bounds on χ'(H) itself; just an algorithm which will find a "good enough" edge-colouring. [I also don't want to place any restrictions on my hypergraphs, except for being k-uniform, and perhaps bounds on the maximum vertex-degree, e.g. Δ(H) ≤ f(k) for some f ∈ ω(1).]
[Addendum. I have now asked a related question on MathOverlow about bounds on the chromatic number, constructive or otherwise.]