**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.