Given a hypergraph H=(V,E), its conflict-free chromatic number (CF-chromatic number) is the minimum number of colors needed to color the vertex set V such that, for every hyperedge S, there is at least one element v \in S whose color is unique (in S). Note that the CF-chromatic number of a hypergraph H is at least its chromatic number (where each hyperedge of size at least two is required to be non-monochromatic), and at most the colorful chromatic number (where each hyperedge is required to be colorful). I will survey some recent results on the conflict-free chromatic number of hypergraphs that arise from certain geometric instances and also present open problems for further research. This ``new" coloring problem is related to the problem of frequency assignment to cellular antennas.
Probability and Combinatorics
Tuesday, January 31, 2006 - 4:00pm
Shakhar Smorodinsky
New York University