We are interested in the class of maps formed of rectangular regions drawn on squared paper (or blocks of cells on a spreadsheet). So the adjacency graph has a natural ordering from the top-left to the bottom right; edges of the graph are unambiguously labelled Horizontal or Vertical; if nodes $B$ and $C$ are both horizontally adjacent to $A$ then they can only be vertically adjacent to each other; etc.
- Is there an upper bound $k$ on the number of colours needed by a greedy colouring of these maps? If so, what is it?
- Can a simple (say, no worse than $O(n^3)$) algorithm do better? Is there such an algorithm with $k = 4$? With $k = 5$?
Best Answer
I'm going to assume that the greedy algorithm orders the rectangles by their top left corner "in reading order": going from top to bottom, and from left to right in each row. Probably other ways of ordering the rectangle produce similar results.
In that case, the greedy algorithm can use arbitrarily many colors. Here is a construction for $5$ colors that can be iterated:
To extend this construction from $k$ colors to $k+1$ colors, take two copies of it, side by side, and:
You should be able to identify the two copies of the $k=4$ construction inside the $k=5$ construction above.
I can't actually think of any shortcuts for coloring these maps that don't work for coloring general planar graphs. However, as for a general planar graph, there is a relatively straightforward (and efficient) $5$-coloring algorithm using Kempe chains: delete a vertex of degree $\le 5$, color the remainder recursively, then put that vertex back and potentially recolor some things to make it fit. (Just as in the proof of the $5$-color theorem.)
There is also, apparently, A Linear Algorithm for Colouring Planar Graphs with Five Colours (Williams, 1985). Finally, I am pretty sure that the proof of the $4$-color theorem extends to pretty efficient algorithm for $4$-coloring planar graphs, but there's naturally going to be lots of casework involved.