We now know that four colors suffice to color every planar map or equivalently to color the vertices of every planar graph. But which of these maps and graphs need only three colors and which only two? The latter question is easily answered; the former is not and is one of the infamous NP-complete problems. Butmany interesting classes of 3-colorable planar graphs are known, and some thing are known about 3-colorable graphs on surfaces, as on the projective plane, torus, Klein bottle, and 17-hole torus. And some variations on coloring have interesting 3-color results, such as list-coloring, invented in part by the late, great Paul Erdős, and extension-coloring, where part of the graph is precolored.
To get in the mood, see if you can determine which of the following five graphs can be 3-colored. A graph can be (properly) 3-colored if one of three colors can be assigned to each vertex so that no adjacent vertices receive the same color. What properties do the 3-colorable graphs have?
[Figure 1] (see right)(Four of the above graphs are formed from the 1-skeleton of a regular Platonic solid.)
Can the two graphs below be (properly) colored with each vertex receiving a color from its associated list? If not, could they be colored if each vertex had a list of at least three colors?
[Figure 2] (see right)Can the graph below be (properly) colored with each vertex receiving a color from its associated list? (Here each triple xyz represents a set of three colors {x, y, z}.)
[Figure 3] (see right)Below are graphs that can be 3-colored. Suppose six vertices are precolored with two colors as shown. How many colors are needed so that this precoloring extends to the entire graph?
[Figure 4] (see right)
