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