Suppose we have a region of the plane tiled by finitely many rectangles. We want to color the rectangles so that two rectangles have different colors if they share a part of an edge or if they share a corner. Let’s say that a graph that arises in this way is called a rectangle graph. What’s the minimum number of colors which suffices for all rectangle graphs? Let's call the answer Chromatic(rectangle).
The answer is 5 or 6 (Theorems 1 and 2 below). Can we close this gap?
Theorem 1. Chromatic(rectangle) is at least 5.
Proof. With apologies for the graphics, figure 1 is a rectangle configuration (with 18 rectangles) which requires 5 colors. Just for fun, figure 2 is another example (also with 18 rectangles).
Figure 1.
+--+--------+-----+
| | | |
| +--+-----+ |
| | | | |
+--+--+--+--+--+--+
| | | | | | |
| | +--+--+ | |
| | | | | | |
+--+--+--+--+--+ |
| | | | |
| +-----+--+--+
| | | |
+-----+-----+-----+
Figure 2.
+--------+--+--+
| | | |
+--+-----+--+ |
| | | | |
+--+--+--+--+ |
| | | | | |
| +--+--+--+ |
| | | | | |
+--+--+--+--+ |
| | | | |
+--+-----+--+ |
| | | |
+--------+--+--+
Theorem 2. Chromatic(rectangle) is at most 6.
Proof. Suppose we have a region of the plane tiled by finitely many polygons (not necessarily rectangles). Two polygons have to have different colors if they share a part of an edge or if they share a corner. A graph that arises in this way is called a map graph [CGP, T]. If at most $k$ polygons meet at a point, it's called a $k$-map graph. A rectangle graph is a 4-map graph. [CGP] section 4 notes that all 4-map graphs are 6-colorable, by [T] and [B].
References
[CGP] Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H., Map graphs, J. ACM 49, No. 2, 127-138 (2002). ZBL1323.05039.
[T] Thorup, Mikkel, Map graphs in polynomial time, 39th annual symposium on foundations of computer science. Proceedings of the symposium (FOCS ’98), Palo Alto, CA, USA, November 8–11, 1998, Los Alamitos, CA: IEEE Computer Society. xiv, 745 396-407 (1998). ZBL0997.68503.
[B] Borodin, Oleg V., A new proof of the 6 color theorem, J. Graph Theory 19, No. 4, 507-521 (1995). ZBL0826.05027.
