Colorful Mathematics: Part III
2. New problems from old ones
a. What plane maps can be face-colored with exactly one color?
b. What plane maps can be face-colored with exactly two colors?
c. What plane maps can be face-colored with exactly three colors?
d. What plane maps can be face-colored with exactly four colors?
(A phrase such as "face-colored with exactly three colors" means that the map can be colored with three, but not fewer, colors.)
Based on the example, can you determine what kind of plane maps can be colored with exactly one color?
An interesting corollary of this theorem is that a map formed by intersecting straight lines in the plane or by circles drawn in the plane can be colored with two colors.
The four-color problem is a problem about plane graphs, so I have formulated the problems above in terms of plane graphs. You may want to see which of the theorems about vertex-colorings apply to graphs which are not planar. Even for plane graphs, determining precisely which such graphs can be vertex-colored with exactly 3 colors is exceedingly complex. (Our theorem above deals not with general plane graphs, but only with graphs whose faces are triangles.) On the negative side it is known that the following decision problem is NP-complete: Can a given plane graph G be 3-colored? This means that it is unlikely that a "fast algorithm" will ever be found which for a given graph answers the question of whether the graph has a vertex three-coloring. On the positive side there are some lovely results about three colorings. Here is an especially nifty result due to H. Grötzsch (1959).
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance