4
$\begingroup$

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.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.