Coloring Planar Homothets and Three-Dimensional Hypergraphs

DOI10.1007/978-3-642-29344-3_11MaRDI QIDQ2894459zbMATH OpenOpenAlexFDO

Authors Jean Cardinal, Matias Korman

Publication date 29 June 2012

Published in LATIN 2012: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1101.0565

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: The inclusion relation between simple objects in the plane may be used to define geometric set systems, or hypergraphs. Properties of various types of colorings of these hypergraphs have been the subject of recent investigations, with applications to wireless networking. We first prove that every set of homothetic copies of a given 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 [18]. As a corollary, we find improvements to well studied variations of the coloring problem such as conflict-free colorings, k-strong (conflict-free) colorings and choosability. We also show a relation between our proof and Schnyder's characterization of planar graphs. Then we show that for any k >1, 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. Furthermore, we also show that at least 2k colors might be necessary. This refines a previous result from Aloupis et al. [2].

Recommendations

• Coloring planar homothets and three-dimensional hypergraphs
• 3-Colorability of plane hypergraphs
• 3-hued coloring of planar graphs
• On colorings of 3-homogeneous hypergraphs in 3 colors
• On 3-colorings of plane graphs
• On \((3,1)^*\)-coloring of plane graphs
• Many 3-colorings of triangle-free planar graphs
• scientific article; zbMATH DE number 2192198
• DP-3-coloring of some planar graphs
• 3-dynamic coloring of planar triangulations

Cited in

(8)

• 3-dynamic coloring of planar triangulations
• Proper coloring of geometric hypergraphs
• Octants are cover-decomposable into many coverings
• On 3-hued coloring of graphs
• Coloring planar homothets and three-dimensional hypergraphs
• Octants are cover-decomposable
• Proper coloring of geometric hypergraphs
• On 3-colorings of plane graphs

This page was built for publication: Coloring Planar Homothets and Three-Dimensional Hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2894459)