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, Carnegie-Mellon 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 3-colorings is achieved by a semi-complete biparite graph. This is joint work with Po-Shen Loh and Benny Sudakov.