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

Oleg Pikhurko, CarnegieMellon University
Fine Hall 224
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 3colorings is achieved by a semicomplete biparite graph. This is joint work with PoShen Loh and Benny Sudakov.