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 work, 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 < K_Q
N^2 where K_Q \approx 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.
Joint work with Oleg Pikhurko and Benny Sudakov.
Copyright. All Rights Reserved.