  Let P_G(q) denote the number of proper q-colorings of a graph G. This
function, called the chromatic polynomial of G, was introduced by Birkhoff in
1912, who sought to attack the famous four-color problem by minimizing P_G(4)
over all planar graphs G. Since then, motivated by a variety of applications,
much research was done on minimizing or maximizing P_G(q) over various families
of graphs.
  In this paper, we study an old problem of Linial and Wilf, to find the graphs
with n vertices and m edges which maximize the number of q-colorings. We
provide the first approach which enables one to solve this problem for many
nontrivial ranges of parameters. Using our machinery, we show that for each q
>= 4 and sufficiently large m < \kappa_q n^2 where \kappa_q is approximately
1/(q log q), the extremal graphs are complete bipartite graphs minus the edges
of a star, plus isolated vertices. Moreover, for q = 3, we establish the
structure of optimal graphs for all large m <= n^2/4, confirming (in a stronger
form) a conjecture of Lazebnik from 1989.
