Non-Monochromatic and Conflict-Free Colorings on Tree Spaces and Planar Network Spaces

Boris Aronov, Mark de Berg, Aleksandar Markovic, Gerhard Woeginger

    Research output: Contribution to journalArticle

    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 (US)
    Pages (from-to)1081-1100
    Number of pages20
    JournalAlgorithmica
    Volume82
    Issue number5
    DOIs
    StatePublished - May 1 2020

    Keywords

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

    ASJC Scopus subject areas

    • Computer Science(all)
    • Computer Science Applications
    • Applied Mathematics

    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