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 contributionAcademicpeer-review

1 Downloads (Pure)

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
Title of host publicationComputing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings
EditorsDaming Zhu, Lusheng Wang
PublisherSpringer
Pages567-578
Number of pages12
ISBN (Print)9783319947754
DOIs
Publication statusPublished - 29 Jun 2018
Event24th International Conference on Computing and Combinatorics Conference, COCOON 2018 - Qing Dao, China
Duration: 2 Jul 20184 Jul 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

Conference

Conference24th International Conference on Computing and Combinatorics Conference, COCOON 2018
CountryChina
CityQing Dao
Period2/07/184/07/18

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

    Aronov, B., de Berg, M., Markovic, A., & Woeginger, G. (2018). Non-monochromatic and conflict-free coloring on tree spaces and planar network spaces. In D. Zhu, & L. Wang (Eds.), Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings (pp. 567-578). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10976 LNCS). Springer. https://doi.org/10.1007/978-3-319-94776-1_47