The goal of a map coloring problem is to color a map so that regions sharing a common border have different colors. (Regions that meet only in a point may share a common color.) Chromatic Number
IMPORTANT IDEA!!!! For example, using the original graph above, we convert each country to a vertex. (We'll use open circles instead of filled dots to make it easier to color them later.) Now we add the edges. Two countries are connected by an edge if and only if they have a common border (but not if they just meet at a point). Note: France shares a common border with each of the other countries except Portugal and Holland. This gives:
In addition, Portugal shares a common border with Spain and Holland shares a common border with Belguim. So, our final graph looks like this:
To "color" a graph, we follow the following vertex coloring rules: Vertex coloring rules
Continuing the example, one way of doing the vertex coloring (that happens to correspond to the colors used in the second map above) is:
Notice that there are many other correct ways of coloring this graph (and hence, the map). Find some more. This same idea can be used to solve other problems; for example, those in which people or things must be grouped or organized based on conflicts among the people or things. In such a situation, the people (or things) are represented by vertices and conflicts between two people (or things) are represented by a connecting edge.
There is a result called Brook's Theorem which is sometimes helpful in putting an upper limit on the chromatic number of a connected graph. Brook's Theorem |