Conflict-free coloring
Conflict-free coloring is a generalization of the notion of graph coloring to hypergraphs.[1]
Definition
[edit]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.
Applications
[edit]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
[edit]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]
External links
[edit]References
[edit]- ^ a b 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
- ^ 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
- ^ 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 graph theory-related article is a stub. You can help Wikipedia by expanding it. |