An Extremal Property of Turan Graphs

作者：Lazebnik Felix^*; Tofts Spencer

来源：Electronic Journal of Combinatorics, 2010, 17(1): R170.

Let F-n,F-tr(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 Turan's 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) : G is an element of F-n,F-tr(n)}. We prove that for all n >= r >= 2, f(n, t(r)(n), r+1) = P-Tr(n)(r+1) and that T-r(n) is the only extremal graph.

• 出版日期2010-12-10