<p>The answer below breaks your condition that you don't want serious restrictions placed on your hypergraph, but it might be of interest if only as related work.</p>
<p>Your hypergraph (which I'll rename as a range space) has a corresponding dual range space (hypergraph) by interchanging the roles of vertices and edges. Your problem then amounts to coloring the elements of this range space so that a range of cardinality <span class="math-container">$r$</span> has <span class="math-container">$r$</span> colors. Let's call such a range colorful.</p>
<p>There's been some recent work on such &quot;colorful coloring&quot; problems for geometric range spaces, motivated partly by problems in sensor networks. A standard question that's asked is:</p>
<blockquote>
<p>Given a parameter <span class="math-container">$k$</span> and range space
<span class="math-container">$S$</span>, determine the function <span class="math-container">$c_S(k)$</span>
such that a <span class="math-container">$c_S(k)$</span> coloring of the
elements of S guarantees that each
range <span class="math-container">$r$</span> of <span class="math-container">$S$</span> has <span class="math-container">$\min(|r|, k)$</span>
colors.</p>
</blockquote>
<p>Thus, <span class="math-container">$c_S(\Delta)$</span> is the quantity you're looking for (where <span class="math-container">$\Delta$</span> is the maximum cardinality of a range).</p>
<p>A related question is to determine <span class="math-container">$c_\tilde{S}(k)$</span>, where <span class="math-container">$\tilde{S}$</span> is the dual range space (in effect, your original hypergraph). <a href="http://di.ulb.ac.be/algo/secollet/papers/ACCLS07c.pdf" rel="nofollow noreferrer">One example of the kind of results obtained is that</a>:</p>
<blockquote>
<p>For <span class="math-container">$S$</span> being the space of halfplanes
in <span class="math-container">$\Re^2$</span>, <span class="math-container">$c_S(k) \le 3k-2$</span></p>
</blockquote>
<p>A good reference for this body of work is the <a href="https://doi.org/10.1007/s00454-008-9116-4" rel="nofollow noreferrer">DCG paper by Aloupsis et al</a>, and the references therein.</p>

CC BY-SA 4.0
2010-09-07T05:34:01.210Z
2022-10-25T07:24:35.023Z
2022-10-25T07:24:35.023Z
Suresh Venkat
<p>Graph colouring problems are, already, <a href="http://en.wikipedia.org/wiki/Graph_coloring#Computational_complexity" rel="nofollow noreferrer">hard enough for most people</a>. Even so, I'm going to have to be difficult and ask a problem about hypergraph colouring.</p>
<h2>Question.</h2>
<p>What efficient algorithms are there for finding an approximately-optimal edge-colouring  for k-uniform hypergraphs?</p>
<p><em>Details ---</em></p>
<ul>
<li><p>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 <em>labelled</em> 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.</p>
</li>
<li><p>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.</p>
</li>
<li><p>I would like results on deterministic or randomized polynomial time algorithms.</p>
</li>
<li><p>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, <em>etc.</em></p>
</li>
</ul>
<p><strong>Edit:</strong> prompted by Suresh's remarks about hypergraph duals below, I should note that this problem is equivalent to the problem of finding a <a href="https://cstheory.stackexchange.com/q/352/248"><em>strong vertex colouring</em></a> of a <em>k-regular</em> 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.
<br><br></p>
<h2>Remarks</h2>
<p>In the case of graphs, <a href="http://en.wikipedia.org/wiki/Vizing%27s_theorem#Properties" rel="nofollow noreferrer"><strong>Vizing's Theorem</strong></a> 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&gt;2 arbitrary.</p>
<p>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 &quot;good enough&quot; 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, <em>e.g.</em> Δ(H) ≤ f(k) for some f ∈ ω(1).]</p>
<p>[<strong>Addendum.</strong> I have now asked <a href="https://mathoverflow.net/questions/38853/bounds-on-strong-vertex-colourings-of-regular-hypergraphs">a related question on MathOverlow</a> about bounds on the chromatic number, constructive or otherwise.]</p>

CC BY-SA 2.5
2010-09-06T21:06:31.380Z
It seems that this problem is sometimes called the _hypergraph packing_.  Does the following page help?  http://en.wikipedia.org/wiki/Packing_in_a_hypergraph
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-06T21:24:34.387Z
I am afraid that the Wikipedia article which I linked in the previous comment may not be a good material to learn about the subject; the terminology is confusing, the same notion is apparently defined more than once, and so on.  I hope that someone knows a better material.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-19T20:02:38.807Z
The asker recently posted a closely related question on MathOverflow: http://mathoverflow.net/questions/38853/bounds-on-strong-vertex-colourings-of-regular-hypergraphs.  @Niel de Beaudrap: Next time you repost a question in a different place, please add links in both directions.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-20T05:30:06.907Z
@Tsuyoshi: Thank you for your continued interest in my problem. I didn't add the link from *here* to *MO* because interest in the topic seemed essentially to have died here, without much progress toward what I would consider to be a satisfactory answer. (In any case, I linked back to this question in the MO question; and priority can be easily established by looking at when it was asked.) —— It's not obvious to me why you feel it is important that I link *reciprocally*, before there are any answers to the question on MO to inform possible answers here; but since you ask, I will do so.
Niel de Beaudrap
CC BY-SA 2.5
2010-10-01T10:55:54.003Z
I will translate my 2 cents from the mathoverflow post back here... the best possible chromatic number for hypergraphs of max degree $\Delta$ and max edge size r is $\Theta(\Delta * r)$, this now appears in a manuscript at http://arxiv.org/abs/1009.6144
daveagp
<co.combinatorics><hypergraphs><graph-colouring>
Efficient algorithm for near-optimal edge-colourings of hypergraphs
Niel de Beaudrap
# Efficient algorithm for near-optimal edge-colourings of hypergraphs

(Asked by: username_0 on 2010-09-06)

Graph colouring problems are, already, [hard enough for most people](http://en.wikipedia.org/wiki/Graph_coloring#Computational_complexity). Even so, I'm going to have to be difficult and ask a problem about hypergraph colouring.

## Question.

What efficient algorithms are there for finding an approximately-optimal edge-colouring for k-uniform hypergraphs?

*Details ---*

* 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*](https://cstheory.stackexchange.com/q/352/248) 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.

## Remarks

In the case of graphs, [**Vizing's Theorem**](http://en.wikipedia.org/wiki/Vizing%27s_theorem#Properties) 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](https://mathoverflow.net/questions/38853/bounds-on-strong-vertex-colourings-of-regular-hypergraphs) about bounds on the chromatic number, constructive or otherwise.]

**Tags:** co.combinatorics, hypergraphs, graph-colouring
> **Comments:**
> **username_1**: It seems that this problem is sometimes called the _hypergraph packing_.  Does the following page help?  http://en.wikipedia.org/wiki/Packing_in_a_hypergraph  
> **username_1**: I am afraid that the Wikipedia article which I linked in the previous comment may not be a good material to learn about the subject; the terminology is confusing, the same notion is apparently defined more than once, and so on.  I hope that someone knows a better material.  
> **username_1**: The asker recently posted a closely related question on MathOverflow: http://mathoverflow.net/questions/38853/bounds-on-strong-vertex-colourings-of-regular-hypergraphs.  @Niel de Beaudrap: Next time you repost a question in a different place, please add links in both directions.  
> **username_0**: @Tsuyoshi: Thank you for your continued interest in my problem. I didn't add the link from *here* to *MO* because interest in the topic seemed essentially to have died here, without much progress toward what I would consider to be a satisfactory answer. (In any case, I linked back to this question in the MO question; and priority can be easily established by looking at when it was asked.) —— It's not obvious to me why you feel it is important that I link *reciprocally*, before there are any answers to the question on MO to inform possible answers here; but since you ask, I will do so.  
> **username_2**: I will translate my 2 cents from the mathoverflow post back here... the best possible chromatic number for hypergraphs of max degree $\Delta$ and max edge size r is $\Theta(\Delta * r)$, this now appears in a manuscript at http://arxiv.org/abs/1009.6144  

---

## 1 answers

### Answer by username_3 on 2010-09-07. Score: 3

The answer below breaks your condition that you don't want serious restrictions placed on your hypergraph, but it might be of interest if only as related work.

Your hypergraph (which I'll rename as a range space) has a corresponding dual range space (hypergraph) by interchanging the roles of vertices and edges. Your problem then amounts to coloring the elements of this range space so that a range of cardinality $r$ has $r$ colors. Let's call such a range colorful.

There's been some recent work on such "colorful coloring" problems for geometric range spaces, motivated partly by problems in sensor networks. A standard question that's asked is:

> Given a parameter $k$ and range space
> $S$, determine the function $c\_S(k)$
> such that a $c\_S(k)$ coloring of the
> elements of S guarantees that each
> range $r$ of $S$ has $\min(|r|, k)$
> colors.

Thus, $c\_S(\Delta)$ is the quantity you're looking for (where $\Delta$ is the maximum cardinality of a range).

A related question is to determine $c\_\tilde{S}(k)$, where $\tilde{S}$ is the dual range space (in effect, your original hypergraph). [One example of the kind of results obtained is that](http://di.ulb.ac.be/algo/secollet/papers/ACCLS07c.pdf):

> For $S$ being the space of halfplanes
> in $\Re^2$, $c\_S(k) \le 3k-2$

A good reference for this body of work is the [DCG paper by Aloupsis et al](https://doi.org/10.1007/s00454-008-9116-4), and the references therein.


---

