Judicious partitions of graphs
type: Item
instance of: scholarly article
title: Judicious partitions of graphs
zbMATH Open document ID: 0796.05056
DOI: 10.1007/BF01876314
author: Béla Bollobás
author: Alex Scott
published in: Periodica Mathematica Hungarica
publication date: 1994-09-05T00:00:00Z
review text: Let \(G\) be a graph and let \(e(G[V_ i])\) be the number of edges of the subgraph of \(G\) induced by \(V_ i\). Set \(p_ k(G) = \min (\max_{1 \leq i \leq k} e(G[V_ i]))\) where the minimum is taken over all partitions \(V_ 1, \dots, V_ k\) of the vertex set of \(G\) into \(k\) sets. It is proved that \(p_ k(G) \leq e(G) / {k+1 \choose 2}\). A better bound is given for graphs with many edges.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05D99
zbMATH DE Number: 508818
zbMATH Keywords: partitions of graphs
zbMATH Keywords: partitions
zbMATH Keywords: bound
reviewed by: Peter Horák
MaRDI profile type: Publication
cites work: Unfriendly partitions of a graph
cites work: Weighted sums of certain dependent random variables
cites work: On a theorem about vertex colorings of graphs
cites work: On an upper bound of the graph's chromatic number, depending on the graph's degree and density
cites work: Some Extremal Properties of Bipartite Subgraphs
cites work: How to make a graph bipartite
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
cites work: A note on bipartite subgraphs of triangle‐free graphs
full work available at URL: https://doi.org/10.1007/bf01876314
OpenAlex ID: W2019647121
description: scientific article; zbMATH DE number 508818