Paper by Erik D. Demaine

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.

BibTeX

@InProceedings{ConflictFree_SODA2017,
  AUTHOR        = {Zachary Abel and Victor Alvarez and Erik D. Demaine and S\'andor Fekete and Aman Gour and Adam Hesterberg and Phillip Keldenich and Christian Scheffer},
  TITLE         = {Three Colors Suffice: Conflict-Free Coloring of Planar Graphs},
  BOOKTITLE     = {Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)},
  bookurl       = {http://siam.org/meetings/da17/},
  ADDRESS       = {Barcelona, Spain},
  MONTH         = {January 16--19},
  YEAR          = 2017,
  PAGES         = {1951--1963},

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.1137/1.9781611974782.127},
  dblp          = {https://dblp.org/rec/conf/soda/AbelADFGHKS17},
  comments      = {This paper is also available as <A HREF="https://arXiv.org/abs/1701.05999">arXiv:1701.05999</A>, and from <A HREF="https://doi.org/10.1137/1.9781611974782.127">SIAM</A>.},
  papers        = {ConflictFree_SIDMA},
}

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.

Comments:

This paper is also available as arXiv:1701.05999, and from SIAM.

Availability:

The paper is available in PDF (504k).

See information on file formats.

[Google Scholar search]

Related papers:

ConflictFree_SIDMA (Conflict-Free Coloring of Graphs)