Computer Science/Discrete Mathematics Seminar I

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. This coloring problem is related to the problem of frequency assignment to cellular antennas, (though the speaker does not encourage individuals to color antennas).