## 6 March 1998:

Algorithms for coloring quadtrees

Brad Hutchings, ICS, UC Irvine

We describe simple linear time algorithms for coloring the
squares of balanced and unbalanced quadtrees so that no two
adjacent squares are given the same color. If squares sharing sides
are defined as adjacent, we color balanced quadtrees with three
colors, and unbalanced quadtrees with four colors; these results
are both tight, as some quadtrees require this many colors. If
squares sharing corners are defined as adjacent, we color balanced
or unbalanced quadtrees with six colors; for some quadtrees, at
least five colors are required.