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

Boris Aronov; Mark T. de Berg; Aleksandar Markovic; Gerhard J. Woeginger

doi:10.48550/arXiv.1805.02538

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

Boris Aronov, Mark T. de Berg, Aleksandar Markovic, Gerhard J. Woeginger

Research output: Contribution to journal › Article › Academic

62 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 language	English
Article number	1805.02538vl
Number of pages	15
Journal	arXiv
Volume	2018
DOIs	https://doi.org/10.48550/arXiv.1805.02538
Publication status	Published - 7 May 2018

Access to Document

10.48550/arXiv.1805.02538

publishers versionFinal published version, 246 KB

Cite this

@article{35d00d78425648a89480c72a9bf33f88,

title = "Non-monochromatic and conflict-free coloring on tree spaces and planar network spaces",

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.",

author = "Boris Aronov and {de Berg}, {Mark T.} and Aleksandar Markovic and Woeginger, {Gerhard J.}",

year = "2018",

month = may,

day = "7",

doi = "10.48550/arXiv.1805.02538",

language = "English",

volume = "2018",

journal = "arXiv",

issn = "2331-8422",

publisher = "Cornell University Library",

}

TY - JOUR

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

AU - Aronov, Boris

AU - de Berg, Mark T.

AU - Markovic, Aleksandar

AU - Woeginger, Gerhard J.

PY - 2018/5/7

Y1 - 2018/5/7

N2 - 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.

AB - 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.

U2 - 10.48550/arXiv.1805.02538

DO - 10.48550/arXiv.1805.02538

M3 - Article

SN - 2331-8422

VL - 2018

JO - arXiv

JF - arXiv

M1 - 1805.02538vl

ER -

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

Abstract

Access to Document

Fingerprint

Cite this