The Maximum Number of Colorings of Graphs of Given Order and
Size

Wilf asked in the 1980s about f(n,m,l), the maximum number of
l-colorings that a graph with n vertices and m edges can have. We
essentially solve this problem for l=3, in particular proving, for all
large n, the conjecture of Lazebnik (1989) that if m\le n^2/4 then the
maximum number of 3-colorings is achieved by a semi-complete biparite
graph. This is joint work with Po-Shen Loh and Benny Sudakov.