Importance: Medium ✭✭
 Author(s): Strausz, Ricardo
 Subject: Graph Theory » Hypergraphs
 Keywords: heterochromatic number
 Prize: A cognac at Coyoacan
 Posted by: Dino on: September 1st, 2007
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.