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.