Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Coloring Planar Homothets and Three-Dimensional Hypergraphs
verfasst von : Jean Cardinal, Matias Korman
Erschienen in: LATIN 2012: Theoretical Informatics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We prove that every finite set of homothetic copies of a given compact and convex body in the plane can be colored with four colors so that any point covered by at least two copies is covered by two copies with distinct colors. This generalizes a previous result from Smorodinsky (SIAM J. Disc. Math. 2007). Then we show that for any
k
≥ 2, every three-dimensional hypergraph can be colored with 6(
k
− 1) colors so that every hyperedge
e
contains min { |
e
|,
k
} vertices with mutually distinct colors. This refines a previous result from Aloupis
et al.
(Disc. & Comp. Geom. 2009). As corollaries, we obtain constant factor improvements for conflict-free coloring,
k
-strong conflict-free coloring, and choosability. Proofs of the upper bounds are constructive and yield simple, polynomial-time algorithms.