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, Gerhard Woeginger

Research output: Contribution to journal › Article › peer-review

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 (US)
Pages (from-to)	1081-1100
Number of pages	20
Journal	Algorithmica
Volume	82
Issue number	5
DOIs	https://doi.org/10.1007/s00453-019-00639-9
State	Published - May 1 2020

Keywords

Conflict-free coloring
Non-monochromatic coloring
Planar networks
Tree

ASJC Scopus subject areas

General Computer Science
Computer Science Applications
Applied Mathematics

Access to Document

10.1007/s00453-019-00639-9

Cite this

@article{55e389bfc99547a29aff792ff3ffe1b3,

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

note = "Publisher Copyright: {\textcopyright} 2020, The Author(s).",

year = "2020",

month = may,

day = "1",

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

language = "English (US)",

volume = "82",

pages = "1081--1100",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

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

UR - http://www.scopus.com/inward/citedby.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

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this