The ACO Seminar (2013–2014)

An old problem of Linial and Wilf asks for the graphs with n vertices and m edges which maximize the number of proper q-colorings of their vertices. In a breakthrough paper, Loh, Pikhurko and Sudakov reduced the problem to an optimization problem. We show that for any instance, the optimization problem always has a solution which corresponds to either a complete multipartite graph or a graph obtained from complete multipartite graph by removing certain edges. We then apply this structural result to general instances, including a conjecture of Lazebnik from 1989 which asserts that for any q≥s≥2, the Turán graph T_s(n) has the maximum number of proper q-coloring among all graphs with the same numbers of vertices and edges. We disprove this by providing infinity many counterexamples (s,q) for s<q<2s. When q=Ω(s²), we show that Turán graph T_s(n) indeed achieves the maximum.

Joint work with Humberto Naves.