The potential to improve the choice: List coloring for geometric hypergraphs
Shakhar Smorodinsky, Ben Gurion University

Given a hypergraph H=(V, E), a coloring of its vertices is said to be conflict-free if for every hyperedge S in E there is at least one vertex whose color is distinct from the colors of all other vertices in S This notion has been studied for several geometric hypergraphs and in various generalizations.
We study the list version of this notion: In this version we are interested in the minimum number k=k(H) such that if each vertex v is associated with a set of colors L_v of size k then one can pick a color for each vertex v from its "list" L_v such that the resulting coloring is conflict-free. Denote this number by ch(H) (the conflict free "choice"number of H). It is easy to see that the minimum number of colors needed for a conflict-free coloring of H is bounded by ch(H).
Let C be some absolute constant. We prove that for hypergraphs H with n vertices which are hereditarily C colorable (in the non-monochromatic sense) we have ch(H) = O(\log n) and this bound is asymptotically tight. Moreover, we show that one can color the vertices of such a hypergraph from lists of size O(\log n) such that the maximum color in any hyperedge is unique. The proof is constructive and uses a suitable potential function for constructing such coloring and analyzing the size of lists needed.
Joint work with Panagiotis Cheilaris and Marek Sulovsky