The extremality of 2-partite Turán graphs with respect to the number of colorings
Date
2021
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
University of Delaware
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).
Description
Keywords
Colorings, Extremal graph, Extremal graph theory, Graph theory, Turán graph