  Coloring unit-disk graphs efficiently is an important problem in the global
and distributed setting, with applications in radio channel assignment problems
when the communication relies on omni-directional antennas of the same power.
In this context it is important to bound not only the complexity of the
coloring algorithms, but also the number of colors used. In this paper, we
consider two natural distributed settings. In the location-aware setting (when
nodes know their coordinates in the plane), we give a constant time distributed
algorithm coloring any unit-disk graph $G$ with at most $4\omega(G)$ colors,
where $\omega(G)$ is the clique number of $G$. This improves upon a classical
3-approximation algorithm for this problem, for all unit-disk graphs whose
chromatic number significantly exceeds their clique number. When nodes do not
know their coordinates in the plane, we give a distributed algorithm in the
LOCAL model that colors every unit-disk graph $G$ with at most
$5.68\omega(G)+1$ colors in $O(\log^* n)$ rounds. This algorithm is based on a
study of the local structure of unit-disk graphs, which is of independent
interest. We conjecture that every unit-disk graph $G$ has average degree at
most $4\omega(G)$, which would imply the existence of a $O(\log n)$ round
algorithm coloring any unit-disk graph $G$ with (approximately) $4\omega(G)$
colors in the LOCAL model. We provide partial results towards this conjecture
using Fourier-analytical tools.
