Date: Monday, November 22, 2004 Time: 4:05 p.m. Room: Little Hall (LIT) 339 (Atrium) Refreshments: 3:30 p.m. in LIT 339

Abstract: Can the countries of a planar map be colored using four colors in such a way that countries sharing a boundary segment (not just a point) receive different colors? This simply stated question, formulated by Francis Guthrie in 1852, turned out to be one of the hardest problems in mathematics.

The history of the problem includes many false proofs, a long list of equivalent formulations and a lot of theory it inspired. A complicated and computer-assisted proof was finally found by Appel and Haken in 1976, but it is not completely satisfactory. A simpler but still computer-assisted proof was obtained by Robertson, Sanders, Seymour and the speaker. The quest for a computer-free proof continues and many conjectured generalizations await resolution.

The talk will discuss all of the above aspects at a level suitable for graduate and advanced undergraduate students.

 ^* Professor Thomas works in Graph Theory, a relatively young field that is becoming increasingly more important, because of applications in other areas of mathematics, physics, chemistry, engineering and social sciences. His work has concentrated on structural results and their use in the design of theoretically efficient and practical graph algorithms. Professor Thomas' results include:

• a new and simpler proof of the Four Color Theorem,
• a proof of Hadwiger's conjecture for K6-free graphs,
• a proof of Sachs' linkless embedding conjecture,
• structure theory for excluding infinite graphs,
• proofs of conjectures of Plummer, Grunbaum, and Nash-Williams concerning Hamiltonian graphs on surfaces,
• a proof of Younger's conjecture about packing directed circuits,
• a solution to a 1913 question of Polya, which also solves the ''even directed circuit problem" and several other equivalent problems.

This featured lecture is being arranged in connection with the Mathematics Department's Special Year in Number Theory and Combinatorics For more information see the website:
http://www.math.ufl.edu/specialyears/2004-5/.