Counting colourings
Dr. David Galvin
University of Pennsylvania

Abstract:

A proper q-colouring of a graph is an assignment of colours to the vertices from a palette of size q in which no two adjacent vertices get the same colour. A general question which may be asked in a variety of forms is: which graphs admit the most q-colourings? In this talk we focus on N-vertex, d-regular bipartite graphs with 2d dividing N. We show that among graphs in this class, the one that admits the most q-colourings is the disjoint union of N/2d complete d-regular bipartite graphs. The proof involves entropy considerations, and extends naturally to graph homomorphisms, a more general type of graph colouring.

This is joint work with Prasad Tetali, Georgia Tech.