### Coloring and Guarding Arrangements

*Prosenjit Bose, Jean Cardinal, Sébastien Collette, Ferran Hurtado, Matias Korman, Stefan Langerman, Perouz Taslakian*

#### Abstract

Given a simple arrangement of lines in the plane, what is the minimum
number c of colors required so that we can color all
lines in a way that no cell of the arrangement is monochromatic? In
this paper we give worst-case bounds on the number c for
both the above question and for some of its variations. Line coloring
problems can be redefined as geometric hypergraph coloring problems as
follows: if we define
H

_{line-cell}as the hypergraph whose vertices are lines and edges are cells of the arrangement, then c is equal to the chromatic number of this hypergraph. Specifically, we prove that this chromatic number is between Ω(log n / log log n) and O(n). Furthermore, we give bounds on the minimum size of a subset S of the intersection points between pairs of lines in A such that every cell contains at least a vertex of S. This may be seen as the problem of guarding cells with vertices when the lines act as obstacles. The problem can also be defined as the minimum vertex cover problem in the hypergraph H_{vertex-cell}, the vertices of which are the line intersections, and the hyperedges are vertices of a cell. Analogously, we consider the problem of touching the lines with a minimum subset of the cells of the arrangement, which we identify as the minimum vertex cover problem in the H_{cell-zone}hypergraph.Full Text: PDF PostScript