Keszegh, Balázs and Pálvölgyi, Dömötör (2017) Proper coloring of geometric hypergraphs. In: 33rd International Symposium on Computational Geometry, SoCG 2017. Leibniz International Proceedings in Informatics, LIPIcs (77). Schloss Dagstuhl Leibniz-Zentrum für Informatik, Dagstuhl, pp. 471-4715. ISBN 9783959770385
|
Text
1612.02158v1.pdf Download (656kB) | Preview |
Abstract
We study whether for a given planar family F there is an m such that any finite set of points can be 3-colored such that any member of F that contains at least m points contains two points with different colors. We conjecture that if F is a family of pseudo-disks, then m = 3 is sufficient. We prove that when F is the family of all homothetic copies of a given convex polygon, then such an m exists. We also study the problem in higher dimensions. © Balázs Keszegh and Dömötör Pálvölgyi.
| Item Type: | Book Section |
|---|---|
| Uncontrolled Keywords: | GEOMETRY; Two-point; Proper coloring; Hypergraph coloring; HIGHER DIMENSIONS; Geometric hypergraphs; Finite set; Convex polygon; Computational geometry; Geometric hypergraph coloring; Discrete geometry; Decomposition of multiple coverings |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 19 Dec 2017 07:13 |
| Last Modified: | 19 Dec 2017 07:13 |
| URI: | http://real.mtak.hu/id/eprint/71208 |
Actions (login required)
 |
Edit Item |
