Research Seminar - April 07, 2000

Seminar Announcement

Abstract

A chromatic polynomial for a graph G is a function that gives the number of ways to colour G with n colours. It is known that the chromiatic polynomial for a graph with k vertices is a monic polynomial of degree k. A natural question to ask is how large a chromatic polynomial can be computed. In 1965 a manual computation of the chromatic polynomial of the planar dual of the truncated icosahedron was reported in the literature. The graph that represents the truncated icosahedron has 32 vertices and 90 edges. Some of the coefficients of its chromatic polynomial are as large as 10^19. For a number of years I have been working to develop an effective computer algorithm that would replicate this result. The talk will describe how the classic delete-contract algorithm has been modified to replicate this result. In the course of this work it became important to think about computation trees in a more general setting. Some of the algorithmic developemnts can be understood by knowing how a computation tree can be dynamically altered. It is hoped that some of the operations on computation trees that have been used can be incorporated into other algorithms.