  Coloring is used in wireless networks to improve communication efficiency,
mainly in terms of bandwidth, energy and possibly end-to-end delays. In this
research report, we define the h-hop node coloring problem, with h any positive
integer. We prove that the associated decision problem is NP-complete. We then
present a 3-hop distributed coloring algorithm that is optimized for dense
networks: a node does not need to exchange the priorities and colors of its
2-hop neighbors. Through simulation results, we highlight the impact of
priority assignment on the number of colors obtained for any network. We then
focus on grids and identify a color pattern that can be reproduced to color the
whole grid. We show how the coloring algorithm can use regularity properties to
obtain a periodic color pattern with the optimal number of colors. We then
consider grids with holes and study how to extend our results.
