**Reference**:- Zachary Abel, Victor Alvarez, Erik D. Demaine, Sándor Fekete, Aman Gour, Adam Hesterberg, Phillip Keldenich, and Christian Scheffer, “Three Colors Suffice: Conflict-Free Coloring of Planar Graphs”, in
*Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)*, Barcelona, Spain, January 16–19, 2017, pages 1951–1963. **Abstract**:-
A
*conflict-free k-coloring*of a graph assigns one of*k*different colors to some of the vertices such that, for every vertex*v*, there is a color that is assigned to exactly one vertex among*v*and*v*'s neighbors. Such colorings have applications in wireless networking, robotics, and geometry, and are well-studied in graph theory. Here we study the natural problem of the*conflict-free chromatic number*χ_{CF}(*G*) (the smallest*k*for which conflict-free*k*-colorings exist), with a focus on planar graphs.For general graphs, we prove the conflict-free variant of the famous Hadwiger Conjecture: If

*G*does not contain*K*_{k+1}as a minor, then χ_{CF}(*G*) ≤*k*. For planar graphs, we obtain a tight worst-case bound: three colors are sometimes necessary and always sufficient. In addition, we give a complete characterization of the algorithmic/computational complexity of conflict-free coloring. It is NP-complete to decide whether a planar graph has a conflict-free coloring with*one*color, while for outerplanar graphs, this can be decided in polynomial time. Furthermore, it is NP-complete to decide whether a planar graph has a conflict-free coloring with*two*colors, while for outerplanar graphs, two colors always suffice. For the bicriteria problem of minimizing the number of colored vertices subject to a given bound*k*on the number of colors, we give a full algorithmic characterization in terms of complexity and approximation for outerplanar and planar graphs. **Availability**:- The paper is available in PDF (504k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.