25
$\begingroup$

The four-colour mapping theorem states that all maps can be four-coloured (adjacent regions receive distinct colours, and four different colours are used in total). However, the technical definition of "map" implies that regions must be contiguous, and, in fact, it's easy to construct counter-examples to a proposed "four-colour not-necessarily-contiguous-mapping conjecture". For example:

alt text

where the two green areas constitute a single non-contiguous region. This is clearly not four-colourable since each of the five internal regions is adjacent to every other (forming a $K_5$ in the graph-theoretic sense).

Some real-world maps have disjoint components (e.g. USA, including Alaska, Hawaii), which leads me to:

Question: What is an example of a real-world map (which necessarily must have at least one non-contiguous region) that is not four-colourable?

  • 8
    There are other conditions in a real world map that may prevent 4-colorability, like regions meeting at a point (e.g., Colorado, Utah, New Mexico, and Arizona meet in a "corner", as do Chad, Niger, Nigeria, and Cameroon; if they were all "inside" another country, you would also end up needing 5 colors; or if you had 5 "slices" meeting at a corner)2011-01-03
  • 0
    Indeed I did miss that (rather important) condition. Although, hopefully the meaning of the question is not lost as a result.2011-01-04
  • 1
    So here is a general problem: You have a map on the sphere. The set of countries is partitioned into nonempty blocks. Two countries in the same block do not touch each other. Color the blocks such that adjacent countries get different colors. How many colors will suffice?2011-01-05

4 Answers 4