We describe simple linear time algorithms for coloring the squares of balan
ced and unbalanced quadtrees so that no two adjacent squares are given the
same color. If squares sharing sides are defined as adjacent, we color bala
nced 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 u
nbalanced quadtrees with six colors; for some quadtrees, at least five colo
rs are required.