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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

199 Downloads (Pure)

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	1081-1100
Aantal pagina's	20
Tijdschrift	Algorithmica
Volume	82
Nummer van het tijdschrift	5
Vroegere onlinedatum	31 okt. 2019
DOI's	https://doi.org/10.1007/s00453-019-00639-9
Status	Gepubliceerd - 1 mei 2020

Financiering

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

Financiers	Financiernummer
National Science Foundation(NSF)	CCF-11-17336, CCF-12-18791, CCF-15-40656
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	024.002.003

Toegang tot document

10.1007/s00453-019-00639-9

publishers versionDefinitieve gepubliceerde versie, 559 KBLicentie: CC BY

Andere bestanden en links

Link to publication in Scopus

Citeer dit

@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 - https://www.scopus.com/pages/publications/85074731029

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

Samenvatting

Financiering

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit