Three Colors Suffice: Conflict-Free Coloring of Planar Graphs

DOI10.1137/1.9781611974782.127zbMath1410.05062OpenAlexW2950671599MaRDI QIDQ4575874

Christian Scheffer, Erik D. Demaine, Sándor P. Fekete, Aman Gour, Phillip Keldenich, Adam Hesterberg, Zachary R. Abel, Victor Alvarez

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974782.127

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (6)

Conflict-Free Coloring of Graphs ⋮ Conflict-Free Coloring of Intersection Graphs ⋮ Conflict-free coloring of intersection graphs of geometric objects ⋮ Conflict-free coloring of string graphs ⋮ Non-monochromatic and conflict-free colorings on tree spaces and planar network spaces ⋮ Unnamed Item

This page was built for publication: Three Colors Suffice: Conflict-Free Coloring of Planar Graphs