Title: Bill Tutte and graph coloring: local and global
| Speaker: | Noga Alon |
| Affiliation: | Tel Aviv University |
| Location: | MC 5501 |
| Reception: | MC 5511 |
Abstract:
Bill Tutte is one of the founders of Graph Theory and Matroid Theory. His interest in graph coloring started early, when already as a student he introduced and studied what we now call the Tutte polynomial, which he called the dichromatic polynomial. During that time he also observed that there are graphs of arbitrarily high chromatic number and no short cycles, a fact demonstrating the global nature of graph coloring. The investigation of these graphs had a profound impact on Graph Theory. It combines combinatorial, probabilistic, algebraic and topological techniques with number theoretic tools. I will describe briefly the rich history of the subject focusing on some recent results.