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.