Conflict-free coloring
From Wikipedia, the free encyclopedia
Conflict-free coloring is a generalization of the notion of graph coloring to hypergraphs.[1]
A hypergraph H has a vertex-set V and an edge-set E. Each edge is a subset of vertices (in a graph, each edge contains at most two vertices, but in a hypergraph, it may contain more than two).
A coloring is an assignment of a color to each vertex of V.
A coloring is conflict-free if at least one vertex in each edge has a unique color. If H is a graph, then this condition becomes the standard condition for a legal coloring of a graph: the two vertices adjacent to every edge should have different colors.
Conflict-free colorings arise in the context of assigning frequency bands to cellular antennae, in battery consumption aspects of sensor networks and in RFID protocols.[1]
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 Kk+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]
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
