The Colorful Helly Property for Hypergraphs

Hellyʹs theorem for convex sets motivated the definition of the p-Helly property for hypergraphs. On the other hand, the colorful Helly theorem for collections of convex sets, by Lovász, generalizes Hellyʹs theorem. Motivated by Lovászʹs theorem, we define the colorful p-Helly property for a family of p hypergraphs. We describe complexity results related to the latter. We show that it is Co-NP-complete to decide if a family of p hypergraphs is colorful p-Helly, even if p = 2 . However, for any fixed p, we describe a polynomial time algorithm to decide if such family is colorful p-Helly, provided p − 1 of the hypergraphs are p-Helly.