Conflict-free coloring of intersection graphs of geometric objects

DOI10.1007/s00454-019-00097-8zbMath1450.05030arXiv1704.02018OpenAlexW2948265309WikidataQ127783361 ScholiaQ127783361MaRDI QIDQ2207603

Chaya Keller, Shakhar Smorodinsky

Publication date: 23 October 2020

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

geometric graphslist coloringconflict-free coloringaxis-parallel rectanglespseudo-discs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (10)

Conflict-Free Coloring of Intersection Graphs ⋮ Conflict-free coloring bounds on open neighborhoods ⋮ The \(\varepsilon\)-\(t\)-net problem ⋮ Conflict‐free chromatic number versus conflict‐free chromatic index ⋮ Coloring intersection hypergraphs of pseudo-disks ⋮ Constructing planar support for non-piercing regions ⋮ Conflict-free coloring of string graphs ⋮ Non-monochromatic and conflict-free colorings on tree spaces and planar network spaces ⋮ Unnamed Item ⋮ Coloring intersection hypergraphs of pseudo-disks

Cites Work

• Approximation algorithms for maximum independent set of pseudo-disks
• Complexity of conflict-free colorings of graphs
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Topological Hypergraphs
• More on decomposing coverings by octants
• On The Chromatic Number of Geometric Hypergraphs
• Conflict-Free Colourings of Graphs and Hypergraphs
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Conflict-Free Coloring of Intersection Graphs
• Three Colors Suffice: Conflict-Free Coloring of Planar Graphs
• Erdos-Hajnal conjecture for graphs with bounded VC-dimension
• Planar Support for Non-piercing Regions and Applications
• Coloring intersection hypergraphs of pseudo-disks
• A Finite Family of Pseudodiscs Must Include a “Small” Pseudodisc
• Conflict-Free Coloring and its Applications
• The potential to improve the choice
• Conflict-Free Colouring of Graphs
• Online Conflict‐Free Coloring for Intervals
• Toward a theory of crossing numbers
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Conflict-free coloring of intersection graphs of geometric objects