License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.32
URN: urn:nbn:de:0030-drops-160401
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16040/
Damásdi, Gábor ;
Pálvölgyi, Dömötör
Three-Chromatic Geometric Hypergraphs
Abstract
We prove that for any planar convex body C there is a positive integer m with the property that any finite point set P in the plane can be three-colored such that there is no translate of C containing at least m points of P, all of the same color. As a part of the proof, we show a strengthening of the Erdős-Sands-Sauer-Woodrow conjecture. Surprisingly, the proof also relies on the two dimensional case of the Illumination conjecture.
BibTeX - Entry
@InProceedings{damasdi_et_al:LIPIcs.SoCG.2022.32,
author = {Dam\'{a}sdi, G\'{a}bor and P\'{a}lv\"{o}lgyi, D\"{o}m\"{o}t\"{o}r},
title = {{Three-Chromatic Geometric Hypergraphs}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {32:1--32:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-227-3},
ISSN = {1868-8969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16040},
URN = {urn:nbn:de:0030-drops-160401},
doi = {10.4230/LIPIcs.SoCG.2022.32},
annote = {Keywords: Discrete geometry, Geometric hypergraph coloring, Decomposition of multiple coverings}
}
|
Keywords: |
|
Discrete geometry, Geometric hypergraph coloring, Decomposition of multiple coverings |
|
Collection: |
|
38th International Symposium on Computational Geometry (SoCG 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
01.06.2022 |
