Colorful Mathematics: Part I

Posted September 2003.

1. Introduction

The first movies, the first television sets, and the first computer monitors had something in common: They showed images only in black and white. There may be an elemental quality, such as in Kurasawa's early films, to using only grays to display images, but since people usually see in color, gray scale images are "artificial" ones. We are used to gray scale images in newspapers, magazines, and bar codes, but increasingly color is being used because the economics and technology necessary to provide information in color have become cost effective.

Like so many other areas, when one thinks about color, mathematics may not be the subject that first comes to mind. Yet mathematicians have used ideas involving distinguishing objects by giving them different colors to great advantage, have studied the physics of color, and have made attempts to understand how different people perceive colors.

The most famous coloring problem that mathematicians have addressed is almost certainly the four-color problem. The problem is to show that any "geographical map" can be colored with 4 or fewer colors so that countries (faces) that share a border (edge) receive different colors. This problem, which was not resolved until 1976, has a long and complex history. It is perhaps a curiosity on which to speculate, in light of the fact that maps were being drawn hundreds of years before 1852, why the issue of the minimum number of colors to color the regions of a geographic map was not raised much earlier than 1852 when Francis Guthrie posed the problem. There is little doubt that one of the major reasons for the growth in interest in graph theory in the first half of the 20th century was directly related to attempts to resolve the four-color conjecture. However, one has to be careful what one means by a geographic map. Is the situation where a country might have more than one piece (as was true for Pakistan until 1971) allowed? For the classical statement of the four-color problem such a situation is not allowed; we are interested in the minimum number of colors which are necessary to color the countries of a "map" drawn in the plane, where the countries consist of only one piece. This is one of the many aspects of considering coloring problems that was made precise by mathematical investigation.

However, mathematicians are rarely content to limit themselves to answering the first question posed. Although the four-color problem originally arose as a problem about coloring the faces of a map, recent discussions of the problem nearly always use terms involved in coloring the vertices of a graph. Generalizing and abstracting open new worlds of interesting questions to pursue. Furthermore, in the case of coloring problems they open unexpected opportunities to solve problems that at first glance have nothing to do with coloring, such as designing a good schedule for final examinations at a college. In this series of articles my goal is to explore a variety of ways that mathematics has investigated colors and "colorings."

Joseph Malkevitch
York College (CUNY)

Email: malkevitch@york.cuny.edu

1. Introduction
2. Basic ideas
3. Face colorings
4. Vertex colorings
5. Some history
6. References