Judicious partitions of graphs (Q1314903): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 02:54, 5 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Judicious partitions of graphs |
scientific article |
Statements
Judicious partitions of graphs (English)
0 references
5 September 1994
0 references
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.
0 references
partitions of graphs
0 references
partitions
0 references
bound
0 references
