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

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

doi:10.1007/978-3-319-94776-1_47

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 proceeding › Conference contribution

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 language	English (US)
Title of host publication	Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings
Editors	Daming Zhu, Lusheng Wang
Publisher	Springer Verlag
Pages	567-578
Number of pages	12
ISBN (Print)	9783319947754
DOIs	https://doi.org/10.1007/978-3-319-94776-1_47
State	Published - 2018
Event	24th International Conference on Computing and Combinatorics Conference, COCOON 2018 - Qing Dao, China Duration: Jul 2 2018 → Jul 4 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10976 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	24th International Conference on Computing and Combinatorics Conference, COCOON 2018
Country/Territory	China
City	Qing Dao
Period	7/2/18 → 7/4/18

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-94776-1_47

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 Verlag. https://doi.org/10.1007/978-3-319-94776-1_47

Non-monochromatic and conflict-free coloring on tree spaces and planar network spaces. / Aronov, Boris; de Berg, Mark; Markovic, Aleksandar et al.
Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings. ed. / Daming Zhu; Lusheng Wang. Springer Verlag, 2018. p. 567-578 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10976 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10976 LNCS, Springer Verlag, pp. 567-578, 24th International Conference on Computing and Combinatorics Conference, COCOON 2018, Qing Dao, China, 7/2/18. https://doi.org/10.1007/978-3-319-94776-1_47

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

Aronov, Boris ; de Berg, Mark ; Markovic, Aleksandar et al. / Non-monochromatic and conflict-free coloring on tree spaces and planar network spaces. Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings. editor / Daming Zhu ; Lusheng Wang. Springer Verlag, 2018. pp. 567-578 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e9f4d4adeabc4429b1a52acf42d8b67d,

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

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

note = "Funding Information: BA has been partially supported by NSF Grants CCF-11-17336, CCF-12-18791, and CCF-15-40656, and by BSF grant 2014/170. MdB and AM are supported by the Netherlands{\textquoteright} Organisation for Scientific Research (NWO) under project no. 024.002.003. Publisher Copyright: {\textcopyright} 2018, Springer International Publishing AG, part of Springer Nature.; 24th International Conference on Computing and Combinatorics Conference, COCOON 2018 ; Conference date: 02-07-2018 Through 04-07-2018",

year = "2018",

doi = "10.1007/978-3-319-94776-1_47",

language = "English (US)",

isbn = "9783319947754",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "567--578",

editor = "Daming Zhu and Lusheng Wang",

booktitle = "Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings",

}

TY - GEN

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

AU - Aronov, Boris

AU - de Berg, Mark

AU - Markovic, Aleksandar

AU - Woeginger, Gerhard

N1 - Funding Information: BA has been partially supported by NSF Grants CCF-11-17336, CCF-12-18791, and CCF-15-40656, and by BSF grant 2014/170. MdB and AM are supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 024.002.003. Publisher Copyright: © 2018, Springer International Publishing AG, part of Springer Nature.

PY - 2018

Y1 - 2018

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

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

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

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

U2 - 10.1007/978-3-319-94776-1_47

DO - 10.1007/978-3-319-94776-1_47

M3 - Conference contribution

AN - SCOPUS:85049675349

SN - 9783319947754

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 567

EP - 578

BT - Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings

A2 - Zhu, Daming

A2 - Wang, Lusheng

PB - Springer Verlag

T2 - 24th International Conference on Computing and Combinatorics Conference, COCOON 2018

Y2 - 2 July 2018 through 4 July 2018

ER -

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

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this