Conflict-free coloring

A common special case is when the vertices are points in the plane, and the edges are subsets of points contained in the same disk. In this setting, a coloring of the points is called conflict-free if, for every closed disk D containing at least one point from the set, there is a color that occurs precisely once. Any conflict-free coloring of every set of n points in the plane uses at least c log n colors, for an absolute constant c > 0. The same is true not only for disks but also for homothetic copies of any convex body.^[2]

Another special case is when the vertices are vertices of a graph, and the edges are sets of neighbors. In this setting, a coloring of the vertices is called conflict-free if, for every vertex v, there is a color that is assigned to exactly one vertex among v and its neighbors. In this setting, the conflict-free variant of the Hadwiger Conjecture holds: If a graph G does not contain K_k+1 as a minor, then it has a conflict-free coloring with at most k colors. For planar graphs, three colors are sometimes necessary and always sufficient for a conflict-free coloring. It is NP-complete to decide whether a planar graph has a conflict-free coloring with one color, and whether a planar graph has a conflict-free coloring with two colors.^[3]

When the hypergraph's edges all contain 3 vertices (a 3-uniform hypergraph), it can be 2-colored if and only if it has Property B. Consider an edge containing 3 vertices, and color the vertices with exactly 2 colors. There will always be a single vertex with one of the two colors.

• Conflict-Free Coloring (Shakhar Smorodinsky) on YouTube