The maximal number of induced \(r\)-partite subgraphs
type: Item
instance of: scholarly article
title: The maximal number of induced \(r\)-partite subgraphs
zbMATH Open document ID: 0819.05034
DOI: 10.1007/BF01787417
author: Béla Bollobás
author: Yoshimi Egawa
author: Guoping Jin
author: Andrew T. Harris
published in: Graphs and Combinatorics
publication date: 1995-05-11T00:00:00Z
review text: Let \(K_ r(t)\) denote the complete \(r\)-partite graph with \(t\) vertices in each class and let \(T_ r(n)\) denote the \(r\)-partite Turán graph with \(n\) vertices. The authors show, among other things, that if \(t> 1+\log r\) then the graph \(T_ r(n)\) is the graph with \(n\) vertices that contains the largest number of induced subgraphs isomorphic to \(K_ r(t)\); moreover, the bound on \(t\) is essentially best possible.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 754146
zbMATH Keywords: induced \(r\)-partite subgraphs
zbMATH Keywords: \(r\)-partite graph
zbMATH Keywords: \(r\)-partite Turán graph
zbMATH Keywords: bound
reviewed by: J. W. Moon
MaRDI profile type: Publication
cites work: The Maximum Number of Strongly Connected Subtournaments*
cites work: Q4830805
cites work: The maximal number of induced complete bipartite graphs
cites work: The inducibility of complete bipartite graphs
cites work: Q5724802
cites work: Q3795701
cites work: On the maximal number of certain subgraphs in \(K_ r\)-free graphs
cites work: On cliques in graphs
cites work: The inducibility of graphs
full work available at URL: https://doi.org/10.1007/bf01787417
OpenAlex ID: W2041193896
description: scientific article; zbMATH DE number 754146