# ¿Are critical k-forests tight?

**Conjecture**

Let be a -uniform hypergraph. If is a critical -forest, then it is a -tree.

We say that a hypergraph is a *-graph* if it is -uniform, and denote its order by and its size by .

Laszlo Lovasz introduced the following concept: a -graph is said to be a *-forest* if for every edge there exists a -colouing such that ; that is, such that *only* the edge receives the colours in its vertices. Clearly a -forest is simply a forest in the usual sense (i.e., an acyclic graph). Lovasz proved that

**Theorem**A -forest has size at most .

On the other hand, Victor Neumann-Lara introduced the following invariant: the *heterochromatic number* of a -graph is the minimum number of colours such that, in every colouring there is an edge wich receives different colours in each of its vertices; that is, there exists such that . If the heterochromatic number and the rank are equal, the hypergraph is said to be *tight*. Clearly a -graph is tight if and only if it is connected. A tight -forest is called a *-tree*.

I can prove the following

**Theorem**If a -forest has size then it is tight — and therefore a -tree.

Finally, we say that a -forest is *critical* if no edge can be added to it without loosing the property of being a -forest; it is maximal (in size) with such a property. Observe that there are critical -forests of size , whenever .

So, the conjecture is to motivate the question: ¿are critical -forests tight?

## Bibliography

* indicates original appearance(s) of problem.

## This has been solved.

See http://arxiv.org/abs/1109.3390