November – 2007 ^December

Motivated by battery consumption in sensor networks we study two hypergraph coloring problems: 1. For a hypergraph $H=(V,E)$ (The elements of E are subsets of V) define the parameter $p=p(k)$ to be the minimum number p for which there exists a coloring of V with k colors such that every hyperedge in E with cardinality at least p(k) contains elements from all color classes. If such a coloring does not exist then we say that $p(k) = \infty$. We show that $p(k) < 4k$ when the vertices of H is a finite set P of points in $R^2$ and E consists of all subsets of P that can be obtained by intersecting P with some closed half-plane.

This improves a previous bound of Pach and Toth of $O(k^2)$

We also study the following parameter: 2. For a hypergraph $H = (V,E)$, Let $c = c(k)$ denote the minimum number c such that there exists a coloring of H with c colors such that every hyperedge with cardinality at least k contains elements from some k distinct colors. We show for example that for some geometrically defined hypergraphs, $c(k) = O(k)$ (When H is the hypergraph defined by intersecting a set of points in $R^3$ with all half spaces, the statement $c(2) = 4$ is equivalent to the Four-Color Theorem)

Joint work with G. Aloupis, J. Cardinal, S Collette and S. langerman from Universite Libre de Bruxelles (ULB)