Colorful Mathematics: Part II
2. Insights into coloring planar graphs
A knowledge of the Jordan Curve Theorem provides a way to tell easily, even for very convoluted polygons. Starting at a point clearly outside the polygon, draw a ray to the (blue) point that avoids the vertices of the polygon, as shown below.
V + F - E = 2
For example, for the map in Figure 1:
The idea of a list-coloring takes a while to get used to. If one has a plane graph isomorphic to that of the regular dodecahedron (a plane 3-valent graph made up of 20 vertices and 12 5-gon faces) and one specifies the colors 1, 2, 3 for the first vertex, colors 4, 5, 6 for the second vertex, etc., then the coloring of the plane graph one gets is a coloring with 12 different colors, though each list has three colors. On the other hand, if one specifies the list 1, 2, 3 as the potential colors for every vertex, then Thomassen's Theorem concerning plane graphs of girth 5 means that one can find a vertex-coloring of the dodecahedron with 3 colors.
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
Comments: Email Webmaster