Maximizing the number of colorings
<-- Return to the list
Date: 03-25-2009
Start Time:
3:00pm
End Time: 4:00pm
Speaker: Po-Shen Loh, Princeton University & University of California: Los Angeles
Location: Mudd 303
ABSTRACT
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 \geq 4$ and sufficiently large $m < \kappa_q n^2$ where $\kappa_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 \leq n^2/4$, confirming (in a stronger form) a conjecture of Lazebnik from 1989.
Joint work with Oleg Pikhurko and Benny Sudakov.