Exact bounds for judicious partitions of graphs
type: Item
instance of: scholarly article
title: Exact bounds for judicious partitions of graphs
zbMATH Open document ID: 0985.05028
author: Béla Bollobás
author: Alex Scott
published in: Combinatorica
publication date: 2000-05-14T00:00:00Z
review text: Extending a result of \textit{C. S. Edwards} [Can. J. Math. 25, 475-485 (1973; Zbl 0229.05129) and Recent Adv. Graph Theory, Proc. Symp. Prague 1974, 167-181 (1975; Zbl 0326.05115)] it is shown that a graph with \(m\) edges has a bipartition with at least \(t=m/2 + (\sqrt{8m+1}-1)/8\) edges and at most \(t/2\) inner edges in either class. This result is sharp for complete graphs of odd order which are the only extremal graphs with no isolated vertices. Similar results are proved for the case of more classes.
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1446785
zbMATH Keywords: extremal graph theory
reviewed by: Péter Komjáth
MaRDI profile type: Publication
full work available at URL: s004939970002
OpenAlex ID: W2082198405
DOI: 10.1007/S004939970002
Recommended article: A bound for judicious \(k\)-partitions of graphs
Recommended article: Judicious partitions of bounded‐degree graphs
Recommended article: Bounds for pairs in judicious partitioning of graphs
Recommended article: On judicious partitions of graphs
Recommended article: Judicious \(k\)-partitions of graphs
Recommended article: Judicious partitions of graphs
Recommended article: On Bounds for the k-Partitioning of Graphs
Recommended article: Bounds for judicious balanced bipartitions of graphs
Recommended article: Judicious partitions of hypergraphs
Recommended article: On a Problem of Judiciousk-Partitions of Graphs
description: scientific article; zbMATH DE number 1446785