Sep. 19, 3:30pm, Wean 8220

Jie Ma, Carnegie Mellon University

Graphs with maximum number of proper*q*-colorings and a conjecture of Lazebnik

Jie Ma, Carnegie Mellon University

Graphs with maximum number of proper

Abstract:

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*^{2}), we show that Turán graph *T*_{s}(*n*) indeed achieves the
maximum.

Joint work with Humberto Naves.