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
The chromatic number is the minimum number of colors necessary to color a map so that regions sharing a common border have different colors

For example, the chromatic number for the map above is 3 since it takes at least 3 colors to color the map so that regions sharing a common border have different colors. Why can't it be done with 2 colors?

IMPORTANT IDEA!!!!
A map coloring problem can be solved by first converting the map into a graph where each region is a vertex and an edge connects two vertices if and only if the corresponding regions share a border. Once a map is converted into a graph, a process called vertex coloring can be used to decide how the map should be colored.

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

• Vertices connected by an edge must be different colors.
• Use the fewest possible number of colors.

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
If v is the largest degree (or valence) of any vertex in a connected graph, G, AND G is not a complete graph nor a circuit of odd length, then the chromatic number of G is less than or equal to v.