ACO The ACO Seminar (2013–2014)

Sep. 19, 3:30pm, Wean 8220
Jie Ma, Carnegie Mellon University
Graphs with maximum number of proper q-colorings and a conjecture of Lazebnik


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 qs≥2, the Turán graph Ts(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=Ω(s2), we show that Turán graph Ts(n) indeed achieves the maximum.

Joint work with Humberto Naves.

Back to the ACO home page