An extremal property of Turán graphs (Q612959)

Summary: Let \({\mathcal F}_{n,t_r(n)}\) denote the family of all graphs on \(n\) vertices and \(t_r(n)\) edges, where \(t_r(n)\) is the number of edges in the Turán graph \(t_r(n)\) -- the complete \(r\)-partite graph on \(n\) vertices with partition sizes as equal as possible. For a graph \(G\) and a positive integer \(\lambda\), let \(P_G(\lambda)\) denote the number of proper vertex colorings of \(G\) with at most \(\lambda\) colors, and let \(f(n, t_r(n),\lambda)= \max\{P_G(\lambda): {\mathcal F}_{n,t_r(n)}\}\). We prove that for all \(n\geq r\geq 2\), \(f(n,t_r(n),r+1)= P_{T_r(n)}(r+1)\) and that \(T_r(n)\) is the only extremal graph.