Conflict-free coloring

Last updated
A conflict-free coloring of the hypergraph using as few colors as possible. The third color is required, because if edges 1 and 2 are each colored with the same two colors, edge 3 will necessarily contain two of each color. Conflict-free coloring.svg
A conflict-free coloring of the hypergraph using as few colors as possible. The third color is required, because if edges 1 and 2 are each colored with the same two colors, edge 3 will necessarily contain two of each color.

Conflict-free coloring is a generalization of the notion of graph coloring to hypergraphs. [1]

Contents

Definition

A hypergraphH 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.

Applications

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]

Special cases

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]

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.

References

  1. 1 2 Smorodinsky, Shakhar (2013), Bárány, Imre; Böröczky, Károly J.; Tóth, Gábor Fejes; Pach, János (eds.), "Conflict-Free Coloring and its Applications", Geometry — Intuitive, Discrete, and Convex: A Tribute to László Fejes Tóth, Bolyai Society Mathematical Studies, vol. 24, Berlin, Heidelberg: Springer, pp. 331–389, arXiv: 1005.3616 , doi:10.1007/978-3-642-41498-5_12, ISBN   978-3-642-41498-5, S2CID   174683 , retrieved 2021-01-20
  2. ↑ Pach, János; Tóth, Géza (2003), Aronov, Boris; Basu, Saugata; Pach, János; Sharir, Micha (eds.), "Conflict-free Colorings", Discrete and Computational Geometry: The Goodman-Pollack Festschrift, Algorithms and Combinatorics, vol. 25, Berlin, Heidelberg: Springer, pp. 665–671, doi:10.1007/978-3-642-55566-4_30, ISBN   978-3-642-55566-4 , retrieved 2021-01-20
  3. ↑ Abel, Zachary; Alvarez, Victor; Demaine, Erik D.; Fekete, Sándor P.; Gour, Aman; Hesterberg, Adam; Keldenich, Phillip; Scheffer, Christian (2018-01-01). "Conflict-Free Coloring of Graphs" . SIAM Journal on Discrete Mathematics. 32 (4): 2675–2702. doi:10.1137/17M1146579. hdl: 1721.1/122951 . ISSN   0895-4801.


This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.