𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Judicious partitions of graphs

✍ Scribed by B. Bollobás; A. D. Scott

Publisher
Springer Netherlands
Year
1993
Tongue
English
Weight
474 KB
Volume
26
Category
Article
ISSN
0031-5303

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Judicious partitions of bounded-degree g
Judicious partitions of bounded-degree graphs
✍ B. Bollobás; A. D. Scott 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 118 KB 👁 1 views

## Abstract We prove results on partitioning graphs __G__ with bounded maximum degree. In particular, we provide optimal bounds for bipartitions __V__(__G__) = __V__~1~ ∪ __V__~2~ in which we minimize {__e__(__V__~1~), __e__(__V__~2~)}. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 131–143, 200

Judicious Partitions of Hypergraphs
Judicious Partitions of Hypergraphs
✍ B. Bollobás; A.D. Scott 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 348 KB

We prove the asymptotically best possible result that, for every integer k 2, every 3-uniform graph with m edges has a vertex-partition into k sets such that each set contains at most (1+o(1)) mÂk 3 edges. We also consider related problems and conjecture a more general result. 1997 Academic Press

Judicious Partitions of 3-uniform Hyperg
Judicious Partitions of 3-uniform Hypergraphs
✍ B. Bollobás; A.D. Scott 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 113 KB

A conjecture of Bollobás and Thomason asserts that, for r ≥ 1, every r -uniform hypergraph with m edges can be partitioned into r classes such that every class meets at least rm/(2r -1) edges. Bollobás, Reed and Thomason [3] proved that there is a partition in which every edge meets at least (1 -1/e

Balanced judicious bipartitions of graph
Balanced judicious bipartitions of graphs
✍ Baogang Xu; Juan Yan; Xingxing Yu 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 149 KB

## Abstract A bipartition of the vertex set of a graph is called __balanced__ if the sizes of the sets in the bipartition differ by at most one. B. Bollobás and A. D. Scott, Random Struct Alg 21 (2002), 414–430 conjectured that if __G__ is a graph with minimum degree of at least 2 then __V__(__G__)

Star partitions of graphs
Star partitions of graphs
✍ Egawa, Y.; Kano, M.; Kelmans, Alexander K. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 78 KB 👁 2 views

Let G be a graph and n ≥ 2 an integer. We prove that the following are equivalent: (i) there is a partition , and (ii) for every subset S of V (G), G \ S has at most n|S| components with the property that each of their blocks is an odd order complete graph.