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

Abstract

Let Tr(n) denote the Turán graph -- the complete r-partite graph on n vertices with partition sizes as equal as possible. The number of edges of Tr(n) is denoted by tr(n). For a simple graph G and a positive integer q, let PG(q) denote the number of proper vertex colorings of G with at most q colors. We prove that for q ∈ {5, 7} and sufficiently large n, PG(q) ≤ PT2(n)(q) for any graph G with n vertices and t2(n) edges, with equality holding if and only if G = T2(n).