REAL

Proper coloring of geometric hypergraphs

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

[img]
Preview
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 Edit Item