  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\'{a}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\geq 5$ and sufficiently large $n$, the
Tur\'{a}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.
