An extremal property of Turán graphs
type: Item
instance of: scholarly article
title: An extremal property of Turán graphs
zbMATH Open document ID: 1204.05046
author: Felix Lazebnik
author: Spencer Tofts
published in: The Electronic Journal of Combinatorics
publication date: 2010-12-16T00:00:00Z
full work available at URL: https://eudml.org/doc/232855
full work available at URL: v17i1r170.html
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C31
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5827419
zbMATH Keywords: Turan graph
zbMATH Keywords: proper vertex coloring
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5827419