An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes

Keszegh, Balázs and Pálvölgyi, Dömötör (2019) An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes. JOURNAL OF COMPUTATIONAL GEOMETRY, 10 (1). pp. 1-26. ISSN 1920-180X

Preview

Text 1410.0258.pdf Available under License Creative Commons Attribution. Download (371kB) | Preview

Abstract

The goal of this paper is to give a new, abstract approach to cover-decomposition and polychromatic colorings using hypergraphs on ordered vertex sets. We introduce an abstract version of a framework by Smorodinsky and Yuditsky, used for polychromatic coloring halfplanes, and apply it to so-called ABA-free hypergraphs, which are a generalization of interval graphs. Using our methods, we prove that (2k - 1)-uniform ABA-free hypergraphs have a polychromatic k-coloring, a problem posed by the second author. We also prove the same for hypergraphs defined on a point set by pseudohalfplanes. These results are best possible. We could only prove slightly weaker results for dual hypergraphs defined by pseudohalfplanes, and for hypergraphs defined by pseudohemispheres. We also introduce another new notion that seems to be important for investigating polychromatic colorings and epsilon-nets, shallow hitting sets. We show that all the above hypergraphs have shallow hitting sets, if their hyperedges are containment-free.

Actions (login required)

Edit Item