Extremal subgraphs for two graphs
type: Item
instance of: scholarly article
title: Extremal subgraphs for two graphs
zbMATH Open document ID: 0554.05037
DOI: 10.1016/0095-8956(85)90070-X
author: Fan Chung
author: Joel Spencer
author: P. Erdős
published in: Journal of Combinatorial Theory. Series B
publication date: 1985-01-01T00:00:00Z
review text: In this paper we study several interrelated extremal graph problems: (i) Given integers \(n,e,m\), what is the largest integer f(n,e,m) such that every graph with \(n\) vertices and \(e\) edges must have an induced m-vertex subgraph with at least \(f(n,e,m)\) edges? (ii) Given integers \(n,e,e'\), what is the largest integer \(g(n,e,e')\) such that any two \(n\)-vertex graphs \(G\) and \(H\), with \(e\) and \(e'\) edges, respectively, must have a common subgraph with at least \(g(n,e,e')\) edges? Results obtained here can be used for solving several questionsrelated to the following graph decomposition problem, previously studied by two of the authors and others. (iii) Given integers \(n,r\), what is the least integer \(t=U(n,r)\) such that for any two \(n\)-vertex \(r\)-uniform hypergraphs \(G\) and \(H\) with the same number of edges the edge set \(E(G)\) of \(G\) can be partitioned into \(E_1,...,E_t\) and the edge set \(E(H)\) of \(H\) can be partitioned into \(E'_1,...,E'_t\) in such a way that for each \(i\), the graphs formed by \(E_i\) and \(E'_i\) are isomorphic.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 00A07
zbMATH DE Number: 3882466
zbMATH Keywords: extremal graph problem
zbMATH Keywords: graph decompositions
zbMATH Keywords: uniform hypergraphs
zbMATH Keywords: unavoidable graphs
Wikidata QID: Q106026250
MaRDI profile type: Publication
cites work: Q3872501
cites work: Minimal decompositions of graphs into mutually isomorphic subgraphs
cites work: Minimal decompositions of hypergraphs into mutually isomorphic subhypergraphs
cites work: On unavoidable graphs
cites work: Unavoidable stars in 3-graphs
cites work: On a Ramsey type theorem
cites work: Q5610920
description: scientific article; zbMATH DE number 3882466