Number of colorings of r-partite Turan graphs

Abstract

Let Fn;tr(n) consist of all simple graphs on n vertices and tr(n) edges, where tr(n) is the number of edges in the Turan's graph Tr(n) -- the complete r-partite graph on n vertices with partition sizes as equal as possible. For a simple graph G and a positive integer, let PG( ) denote the number of proper vertex colorings of G with at most . colors, and let f(n, tr(n); ) = maxfPG( ): G . Fn;tr(n)g. We prove that for all n = r = 2, f(n, tr(n);r +1) = PTr(n)(r + 1) and that Tr(n) is the only extremal graph.