Announcing

Math 581: Topics in Graph Theory

Spring 1999

Instructor: Tom Zaslavsky

This is an introductory course for graduate students. That means you needn't know any graph theory beforehand, but you need the kind of mathematical sophistication that comes from an undergraduate math major and some graduate study.

We will study from lectures and a very nicely written, lively, and moderately priced book by Martin Aigner, Graph Theory: A Development from the 4-Color Problem (available in the library for your perusal). The Four-Color Problem is one of the most famous and accessible problems in mathematics. In case you missed it: prove that any map can be colored with only 4 colors so that no two countries with a common boundary have the same color.¹ This was solved after nearly 100 years, but in the meantime it led to a tremendous amount of highly interesting mathematics; from the book you can learn quite a lot about most of the main topics of modern graph theory, which is one reason I like it.

The class will be based on lectures, readings, homework, and discussions. The grade will be based on class contributions, homework, individual meetings with the instructor, and possibly one or two exams.

The probable time for the class is MWF 1:10-2:10 and Tu 1:15-2:40.

¹ Here is some extra detail on the 4-Color Problem. One has to assume that every country is connected. Having just a point in common, like Arizona and Colorado, doesn't count as a common boundary. The question came up first, if I remember rightly, in coloring the counties of England--the equivalent of coloring our 48 states. First homework questions (these are for fun): Does the map of states satisfy the hypotheses of the theorem? Can you color the states in 4 colors? Can you color the world map in 4 colors? (The oceans have to be colored too, but separate seas can be different colors; this isn't all that much like real map coloring but it's a great math problem.)

The textbook will cost $31.00 (after discount and shipping/handling; list price is $36.00) if ordered and paid for by the end of class Tuesday 1/26.

If you aren't ready to order then, I'll take a second order next week but the price will be higher (by no more than $2.50) due to economies of scale in shipping.

Course home page.

My home page.