Non-monochromatic and conflict-free colorings on tree spaces and planar network spaces

Boris Aronov, Mark de Berg, Aleksandar Markovic (Corresponding author), Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

8 Downloads (Pure)

Abstract

It is well known that any set of n intervals in R1 admits a non-monochromatic coloring with two colors and a conflict-free coloring with three colors. We investigate generalizations of this result to colorings of objects in more complex 1-dimensional spaces, namely so-called tree spaces and planar network spaces.

Original languageEnglish
Pages (from-to)1081-1100
Number of pages20
JournalAlgorithmica
Volume82
Issue number5
Early online date31 Oct 2019
DOIs
Publication statusPublished - 1 May 2020

Keywords

  • Conflict-free coloring
  • Non-monochromatic coloring
  • Planar networks
  • Tree

Fingerprint Dive into the research topics of 'Non-monochromatic and conflict-free colorings on tree spaces and planar network spaces'. Together they form a unique fingerprint.

  • Cite this