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

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

doi:10.1007/s00453-019-00639-9

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 journal › Article › Academic › peer-review

181 Downloads (Pure)

Abstract

It is well known that any set of n intervals in R¹ 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
Pages (from-to)	1081-1100
Number of pages	20
Journal	Algorithmica
Volume	82
Issue number	5
Early online date	31 Oct 2019
DOIs	https://doi.org/10.1007/s00453-019-00639-9
Publication status	Published - 1 May 2020

Funding

Bonfils-Stanton Foundation Acronym: BSF Funding numbers: 2014/170

Funders	Funder number
National Science Foundation	CCF-11-17336, CCF-12-18791, CCF-15-40656
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	024.002.003

Keywords

Conflict-free coloring
Non-monochromatic coloring
Planar networks
Tree

Access to Document

10.1007/s00453-019-00639-9

publishers versionFinal published version, 559 KBLicence: CC BY

Cite this

@article{5bbce4cda46c422eacd9a082316a5bfe,

title = "Non-monochromatic and conflict-free colorings 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.",

keywords = "Conflict-free coloring, Non-monochromatic coloring, Planar networks, Tree",

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

year = "2020",

month = may,

day = "1",

doi = "10.1007/s00453-019-00639-9",

language = "English",

volume = "82",

pages = "1081--1100",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer",

number = "5",

}

TY - JOUR

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

AU - Aronov, Boris

AU - de Berg, Mark

AU - Markovic, Aleksandar

AU - Woeginger, Gerhard

PY - 2020/5/1

Y1 - 2020/5/1

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.

KW - Conflict-free coloring

KW - Non-monochromatic coloring

KW - Planar networks

KW - Tree

UR - http://www.scopus.com/inward/record.url?scp=85074731029&partnerID=8YFLogxK

U2 - 10.1007/s00453-019-00639-9

DO - 10.1007/s00453-019-00639-9

M3 - Article

AN - SCOPUS:85074731029

SN - 0178-4617

VL - 82

SP - 1081

EP - 1100

JO - Algorithmica

JF - Algorithmica

IS - 5

ER -

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

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this