{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:37Z","timestamp":1740109297900,"version":"3.37.3"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,10,31]],"date-time":"2019-10-31T00:00:00Z","timestamp":1572480000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,10,31]],"date-time":"2019-10-31T00:00:00Z","timestamp":1572480000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["024.002.003."],"award-info":[{"award-number":["024.002.003."]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-11-17336","CCF-12-18791"],"award-info":[{"award-number":["CCF-11-17336","CCF-12-18791"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-15-40656"],"award-info":[{"award-number":["CCF-15-40656"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100001005","name":"Bonfils-Stanton Foundation","doi-asserted-by":"publisher","award":["2014\/170"],"award-info":[{"award-number":["2014\/170"]}],"id":[{"id":"10.13039\/100001005","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:title>Abstract<\/jats:title>\n<jats:p>It is well known that any set of <jats:italic>n<\/jats:italic> intervals in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb {R} ^1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mrow><mml:mi>R<\/mml:mi><\/mml:mrow><mml:mn>1<\/mml:mn><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula> 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.<\/jats:p>","DOI":"10.1007\/s00453-019-00639-9","type":"journal-article","created":{"date-parts":[[2019,10,31]],"date-time":"2019-10-31T11:16:37Z","timestamp":1572520597000},"page":"1081-1100","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Non-Monochromatic and Conflict-Free Colorings on Tree Spaces and Planar Network Spaces"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3110-4702","authenticated-orcid":false,"given":"Boris","family":"Aronov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"de Berg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3524-7540","authenticated-orcid":false,"given":"Aleksandar","family":"Markovic","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerhard","family":"Woeginger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,10,31]]},"reference":[{"key":"639_CR1","first-page":"2138","volume":"21","author":"MA Abam","year":"2014","unstructured":"Abam, M.A., Rezaei Seraji, M.J., Shadravan, M.: Online conflict-free coloring of intervals. Sci. Iran. 21, 2138\u20132141 (2014)","journal-title":"Sci. Iran."},{"key":"639_CR2","doi-asserted-by":"crossref","unstructured":"Abel, Z., Alvarez, V., Demaine, E.D., Fekete, S.P., Gour, A., Hesterberg, A., Keldenich, P., Scheffer, C.: Three colors suffice: Conflict-free coloring of planar graphs. In: Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1951\u20131963. (2017)","DOI":"10.1137\/1.9781611974782.127"},{"key":"639_CR3","doi-asserted-by":"crossref","unstructured":"Alon, N., Smorodinsky, S.: Conflict-free colorings of shallow discs. In: Proceedings of the 22nd ACM Symposium on Computational Geometry (SoCG), pp. 41\u201343. (2006)","DOI":"10.1145\/1137856.1137864"},{"key":"639_CR4","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Deogun, J.S., Jansen, K., Kloks, T., Kratsch, D., M\u00fcller, H., Tuza, Z.: Ranking of graphs. In: Proceedings of the 20th Workshop. Graph Theory Concepts Computer Science (WG), pp. 292\u2013304. (1994)","DOI":"10.1007\/3-540-59071-4_56"},{"key":"639_CR5","doi-asserted-by":"publisher","first-page":"1342","DOI":"10.1137\/S0097539704446682","volume":"36","author":"K Chen","year":"2007","unstructured":"Chen, K., Fiat, A., Kaplan, H., Levy, M., Matou\u0161ek, J., Mossel, E., Pach, J., Sharir, M., Smorodinsky, S., Wagnerand, U., Welzl, E.: Online conflict-free coloring for intervals. SIAM J. Comput. 36, 1342\u20131359 (2007)","journal-title":"SIAM J. Comput."},{"key":"639_CR6","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0196-6774(81)90031-6","volume":"2","author":"N Chiba","year":"1981","unstructured":"Chiba, N., Nishizeki, T., Saito, N.: A linear 5-coloring algorithm of planar graphs. J. Alg. 2, 317\u2013327 (1981)","journal-title":"J. Alg."},{"key":"639_CR7","unstructured":"de Berg, M., Leijsen, T., Markovic, A., van Renssen, A., Roeloffzen, M., Woeginger, G.J.: Fully dynamic and kinetic conflict-free coloring of intervals with respect to points. In: Proceedings of the 28th International Symposium on Symbolic and Algebraic Computation (ISAAC), pp. 26:1\u201326:13. (2017)"},{"key":"639_CR8","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1137\/S0097539702431840","volume":"33","author":"G Even","year":"2003","unstructured":"Even, G., Lotker, Z., Ron, D., Smorodinsky, S.: Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM J. Comput. 33, 94\u2013136 (2003)","journal-title":"SIAM J. Comput."},{"key":"639_CR9","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s00454-005-1162-6","volume":"34","author":"S Har-Peled","year":"2005","unstructured":"Har-Peled, S., Smorodinsky, S.: Conflict-free coloring of points and simple regions in the plane. Discret. Comput. Geom. 34, 47\u201370 (2005)","journal-title":"Discret. Comput. Geom."},{"key":"639_CR10","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0012-365X(93)E0216-Q","volume":"142","author":"M Katchalski","year":"1995","unstructured":"Katchalski, M., McCuaig, W., Seager, S.M.: Ordered colourings. Discret. Math. 142, 141\u2013154 (1995)","journal-title":"Discret. Math."},{"key":"639_CR11","doi-asserted-by":"publisher","first-page":"2397","DOI":"10.1137\/1.9781611975031.154","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Chaya Keller","year":"2018","unstructured":"Keller, C., Smorodinsky, S.: Conflict-free coloring of intersection graphs of geometric objects In: Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.2397\u20132411. (2017)"},{"key":"639_CR12","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1017\/S0963548309990290","volume":"18","author":"J Pach","year":"2009","unstructured":"Pach, J., Tardos, G.: Conflict-free colourings of graphs and hypergraphs. Comb. Probab. Comput. 18, 819\u2013834 (2009)","journal-title":"Comb. Probab. Comput."},{"key":"639_CR13","doi-asserted-by":"crossref","unstructured":"Robertson, N., Sanders, D.P., Seymour, P., Thomas, R.: Efficiently four-coloring planar graphs. In: Proceedings of the 28th ACM Symposium on Theory of Computing (STOC), pp. 571\u2013575. (1996)","DOI":"10.1145\/237814.238005"},{"key":"639_CR14","unstructured":"Smorodinsky, S.: Combinatorial problems in computational geometry. Ph.D. thesis, Tel-Aviv University (2003)"},{"key":"639_CR15","doi-asserted-by":"crossref","unstructured":"Smorodinsky, S.: On the chromatic number of some geometric hypergraphs. In: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 316\u2013323. (2006)","DOI":"10.1145\/1109557.1109593"},{"key":"639_CR16","unstructured":"Smorodinsky, S.: Conflict-free coloring and its applications. In: B\u00e1r\u00e1ny, I., B\u00f6r\u00f6czky, K.J., T\u00f3th, G.F., Pach, J.: (eds.) Geometry \u2014 Intuitive, Discrete, and Convex: A Tribute to L\u00e1szl\u00f3 Fejes T\u00f3th, pp. 331\u2013389. Springer (2013). See also arXiv:1005.3616"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00639-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00639-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00639-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,30]],"date-time":"2020-10-30T00:12:59Z","timestamp":1604016779000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00639-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,31]]},"references-count":16,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["639"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00639-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,10,31]]},"assertion":[{"value":"8 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 October 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}