The extremality of 2-partite Turán graphs with respect to the number of colorings

Abstract

We consider a problem proposed by Linial and Wilf to determine the structure of graphs that allows the maximum number of $q$-colorings among graphs with $n$ vertices and $m$ edges. Let $T_r(n)$ denote the Turán graph - the complete $r$-partite graph on $n$ vertices with partition sizes as equal as possible. We prove that for all odd integers $q\ge 5$ and sufficiently large $n$, the Turán graph $T_2(n)$ has at least as many $q$-colorings as any other graph $G$ with the same number of vertices and edges as $T_2(n)$, with equality holding if and only if $G=T_2(n)$. Our proof builds on methods by Norine and by Loh, Pikhurko, and Sudakov, which reduces the problem to a quadratic program.