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

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

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    It is well known that any set of n intervals in (Formula Presented) 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)
    Title of host publicationComputing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings
    EditorsDaming Zhu, Lusheng Wang
    PublisherSpringer Verlag
    Pages567-578
    Number of pages12
    ISBN (Print)9783319947754
    DOIs
    StatePublished - 2018
    Event24th International Conference on Computing and Combinatorics Conference, COCOON 2018 - Qing Dao, China
    Duration: Jul 2 2018Jul 4 2018

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume10976 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other24th International Conference on Computing and Combinatorics Conference, COCOON 2018
    CountryChina
    CityQing Dao
    Period7/2/187/4/18

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

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

    Cite this