Conflict-Free Coloring of Graphs

DOI10.1137/17M1146579zbMath1400.05060arXiv1701.05999MaRDI QIDQ4556952

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

Publication date: 28 November 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1701.05999

zbMATH Keywords

complexityplanar graphsworst-case boundsconflict-free coloring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (11)

Conflict-free coloring bounds on open neighborhoods ⋮ Structural parameterization for minimum conflict-free colouring ⋮ A tight bound for conflict-free coloring in terms of distance to cluster ⋮ Colouring a dominating set without conflicts: \(q\)-subset square colouring ⋮ Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth ⋮ On odd colorings of planar graphs ⋮ Odd coloring of sparse graphs and planar graphs ⋮ A Short Note on Open-Neighborhood Conflict-Free Colorings of Graphs ⋮ Parameterized Complexity of Conflict-Free Graph Coloring ⋮ Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods ⋮ Conflict-free coloring: graphs of bounded clique width and intersection graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors
• Complexity of conflict-free colorings of graphs
• Strong conflict-free coloring for intervals
• Graph unique-maximum and conflict-free colorings
• Conflict-free coloring of unit disks
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• The four-colour theorem
• A linear algorithm for the domination number of a series-parallel graph
• Conflict-free coloring of points and simple regions in the plane
• Exact and FPT Algorithms for Max-Conflict Free Coloring in Hypergraphs
• Minimum-weight triangulation is NP-hard
• Conflict-Free Colourings of Graphs and Hypergraphs
• Conflict-Free Coloring Made Stronger
• Polynomial-time data reduction for dominating set
• Approximation algorithms for NP-complete problems on planar graphs
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Three Colors Suffice: Conflict-Free Coloring of Planar Graphs
• Online Conflict-Free Colouring for Hypergraphs
• The potential to improve the choice
• Conflict-Free Colouring of Graphs
• Online Conflict‐Free Coloring for Intervals
• Conflict-Free Colorings of Rectangles Ranges

This page was built for publication: Conflict-Free Coloring of Graphs