An Abstract Approach to Polychromatic Coloring: Shallow Hitting Sets in ABA-free Hypergraphs and Pseudohalfplanes

DOI10.1007/978-3-662-53174-7_19zbMath1417.05069arXiv1410.0258OpenAlexW1669669820MaRDI QIDQ2827816

Balázs Keszegh, Dömötör Pálvölgyi

Publication date: 21 October 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15)

Related Items (5)

Unsplittable coverings in the plane ⋮ Coloring intersection hypergraphs of pseudo-disks ⋮ Coloring Hypergraphs Defined by Stabbed Pseudo-Disks and ABAB-Free Hypergraphs ⋮ Proper coloring of geometric hypergraphs ⋮ Coloring intersection hypergraphs of pseudo-disks

Cites Work

• Octants are cover-decomposable
• Coloring half-planes and bottomless rectangles
• Indecomposable coverings with concave polygons
• Polychromatic coloring for half-planes
• Convex polygons are self-coverable
• Indecomposable coverings with homothetic polygons
• Convex polygons are cover-decomposable
• Octants are cover-decomposable into many coverings
• Convexity in topological affine planes
• Making triangles colorful
• Oriented Matroids
• Decomposing Coverings and the Planar Sensor Cover Problem
• Making Octants Colorful and Related Covering Decomposition Problems

This page was built for publication: An Abstract Approach to Polychromatic Coloring: Shallow Hitting Sets in ABA-free Hypergraphs and Pseudohalfplanes