# Princeton Discrete Math Seminar

## Title:

On a strengthening of Brooks' Theorem

## Speaker:

- Bruce Reed
- C.N.R.S. (Paris)

## Place:

- Fine Hall 224
- Princeton University, Princeton, NJ

## Time:

- 2:30 PM
- Wednesday, October 16, 1996

Abstract:
In 1852, Guthrie asked if every planar map could
be coloured with four colours. This was finally settled in the
affirmative by Haken and Appel in the '70s. This is just one of many
difficult questions concerning the chromatic number of graphs (the
chromatic number of a graph is the minimum number of colours needed to
colour the vertices so that the endpoints of every edge get different
colours). A trivial greedy algorithm shows that if every vertex in a
graph G is adjacent to at most D other vertices then the graph
can be coloured using D + 1 colours. In 1943, Brooks strengthened
this result by showing that if a connected graph is neither a clique (a
set of pairwise adjacent vertices) nor an odd cycle, then its chromatic
number is at most D. We improve on Brooks' result by bounding the
chromatic number by a convex combination of D + 1 and the number of
vertices in a largest clique. We present some applications, which include
answering a question of Erdos and Nesetril. The proof techniques are
probabilistic. Some of the work is joint with Mike Molloy.

contact Paul Seymour (pds@math.princeton.edu).

dimacs-www@dimacs.rutgers.edu
Document last modified on October 14, 1996