NB: A PDF version of this announcement (suitable for posting) is also available.

Coloring and Distinguishing Graphs

Karen L. Collins
Wesleyan University

Thursday, April 14, 2005
L02 Carson Hall, 4 pm
Tea 3:30 pm, Math Lounge

Abstract: Although the problem of finding the chromatic number of a general graph is intractable, Brooks' Theorem says that the chromatic number of a connected graph G is bounded by 1 + D, where D is the maximum degree of G. The chromatic number of a subgraph of G must be less than or equal to the chromatic number of G, so chromatic number is hereditary in this sense. In contrast, Brooks-type theorems very similar to those for the chromatic number exist for two non-hereditary, Burnside-flavored, contrasting parameters, the distinguishing number and the chromatic distinguishing number, all of which will be described in this talk.

This talk will be accessible to graduate students.