𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Judicious partitions of bounded-degree graphs

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

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
118 KB
Volume
46
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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, 2004

📜 SIMILAR VOLUMES

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

Polychromatic colorings of bounded degre
Polychromatic colorings of bounded degree plane graphs
✍ Elad Horev; Roi Krakovski 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 289 KB

## Abstract A __polychromatic k__‐__coloring__ of a plane graph __G__ is an assignment of __k__ colors to the vertices of __G__ such that every face of __G__ has __all k__ colors on its boundary. For a given plane graph __G__, one seeks the __maximum__ number __k__ such that __G__ admits a polychro

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__)

Large P4-free graphs with bounded degree
Large P4-free graphs with bounded degree
✍ Myung S. Chung; Douglas B. West 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 424 KB

## Abstract Let __ex__ \* (__D__; __H__) denote the maximum number of edges in a connected graph with maximum degree __D__ and no induced subgraph isomorphic to __H.__ We prove that this is finite only when __H__ is a disjoint union of paths,m in which case we provide crude upper and lower bounds.