Maximizing the number of q-colorings

Let PG(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 PG(4) over all planar graphs G. Since then, motivated by a variety of applications, much research was done on minimizing or maximizing PG(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 that 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 < κq n2, where κq ≈ 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 ≤ n2/4, confirming (in a stronger form) a conjecture of Lazebnik from 1989