Mondrian Four-Coloring

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

Any planar map can be colored with four colors so that no two regions of the same color touch each other.

[more]

This Demonstration uses the following method to four-color each map:

1. A map of rectangles is converted to a cubic graph (not shown).

2. Cycle set is a non-unique Hamiltonian cycle. Color its edges with two colors.

3. Eliminate one color of and color the edges that are not in in a third color. The result is a cycle set in two colors.

4. and form the boundaries of two regions and

5. Four cases leads to four possible colors for a rectangle, according to whether it is inside or outside or .

The method does not always work, since some cubic graphs exist that are not Hamiltonian. They are still four-colorable, but not by this method.

[less]

Contributed by: Ed Pegg Jr (July 2010)
Open content licensed under CC BY-NC-SA


Snapshots


Details

Ed Pegg Jr, "Math Games: Square Packing," Dec. 1, 2003.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send