Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Conflict-Free Coloring of Intersection Graphs   A conflict-free $k$-coloring of a graph $G=(V,E)$ assigns one of $k$
different colors to some of the vertices such that, for every vertex $v$, there
is a color that is assigned to exactly one vertex among $v$ and $v$'s
neighbors. Such colorings have applications in wireless networking, robotics,
and geometry, and are well studied in graph theory. Here we study the
conflict-free coloring of geometric intersection graphs. We demonstrate that
the intersection graph of $n$ geometric objects without fatness properties and
size restrictions may have conflict-free chromatic number in $\Omega(\log
n/\log\log n)$ and in $\Omega(\sqrt{\log n})$ for disks or squares of different
sizes; it is known for general graphs that the worst case is in $\Theta(\log^2
n)$. For unit-disk intersection graphs, we prove that it is NP-complete to
decide the existence of a conflict-free coloring with one color; we also show
that six colors always suffice, using an algorithm that colors unit disk graphs
of restricted height with two colors. We conjecture that four colors are
sufficient, which we prove for unit squares instead of unit disks. For interval
graphs, we establish a tight worst-case bound of two.

11
The categories of this paper are: hep-lat
21
The categories of this paper are: adap-org
10
The categories of this paper are: q-bio
13
The categories of this paper are: quant-ph
15
The categories of this paper are: nucl-ex
30
The categories of this paper are: q-alg
19
The categories of this paper are: eess
2
The categories of this paper are: math
32
The categories of this paper are: atom-ph
28
The categories of this paper are: alg-geom
16
The categories of this paper are: stat
35
The categories of this paper are: mtrl-th
23
The categories of this paper are: solv-int
36
The categories of this paper are: cmp-lg
9
The categories of this paper are: nlin
25
The categories of this paper are: patt-sol