THE EXTREMALITY OF 2-PARTITE TURAN GRAPHS WITH RESPECT TO THE NUMBER OF COLORINGS

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 Turan graph-the complete r-partite graph on n vertices with partition sizes as equal as possible. We prove that for all odd integers q >= 5 and sufficiently large n, the Turan 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.

Automated summary

This paper discusses the impact of graph structure on the maximum number of q-colorings and proves that under certain conditions, a specific type of graph has the maximum number of q-colorings.