Coloring Graphs/Maps
In the section "The Development", we talked a little bit about the four-color problem. In this section, we will talk more about that and similar problems. But first, we need
to define a few things.
A k-coloring of a graph, G, without loops is an assignment of k colors to the vertices of G, such that adjacent vertices are assigned different colors. If G has a k-coloring,
then G is said to be k-colorable. The chromatic number of G is the smallest number k for which G is k-colorable. It is also possible to have k-edge-colorable
graphs. Graphs that are k-edge-colorable are similar to k-colorable graphs, expect that instead of trying to color the vertices, you are trying to color the edges.
Check out this applet to try to color some vertices.
Knowing these two things helps us to be able to generalize to regions. This is where the four-color problem and coloring maps come in. Coloring maps asks the question: "how many
colors are needed to color the entire map"? The four-color problem states that any map can be colored in just four colors, and as you found out from "The Development", this took a
long time to prove. Check out the website below to play around with and try a few coloring maps of your own.
http://www.nikoli.com/en/take_a_break/four_color_problem/
If you would like to learn more about the four color problem, visit:
https://nrich.maths.org/6291