On several partitioning problems of Bollobás and Scott

DOI10.1016/j.jctb.2010.06.002zbMath1208.05115OpenAlexW1965767573MaRDI QIDQ602718

Xingxing Yu, Pei-Lan Yen, Jie Ma

Publication date: 5 November 2010

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2010.06.002

zbMATH Keywords

Azuma-Hoeffding inequalityjudicious partitiongraph partition

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

On judicious partitions of uniform hypergraphs ⋮ Judicious bisection of hypergraphs ⋮ Judicious partitions of weighted hypergraphs ⋮ Biased partitions and judicious \(k\)-partitions of graphs ⋮ On judicious bipartitions of directed graphs ⋮ Judicious partitions of directed graphs ⋮ Bounds for pairs in judicious partitioning of graphs ⋮ Partitioning digraphs with outdegree at least 4 ⋮ On bisections of graphs without complete bipartite graphs ⋮ Graph partitioning: an updated survey ⋮ Bisections of Graphs Without Short Cycles ⋮ Partitioning dense uniform hypergraphs ⋮ Optimal bisections of directed graphs ⋮ The Bollobás--Scott Conjecture for 4-Uniform Hypergraphs ⋮ Judicious Partitioning of Hypergraphs with Edges of Size at Most 2 ⋮ Bisections of graphs ⋮ Maximum cuts in \(\mathscr{H} \)-free graphs ⋮ On bipartitions of directed graphs with small semidegree ⋮ Simple probabilistic analysis to generalize bottleneck graph multi-partitioning ⋮ Bipartitions of oriented graphs ⋮ On partitions of \(K_{2, 3}\)-free graphs under degree constraints ⋮ A bound on judicious bipartitions of directed graphs ⋮ On a Problem of Judiciousk-Partitions of Graphs ⋮ Partitioning 3-uniform hypergraphs ⋮ Maximum bipartite subgraphs in graphs without short cycles ⋮ On judicious partitions of hypergraphs with edges of size at most 3

Cites Work

• Judicious \(k\)-partitions of graphs
• On a bottleneck bipartition conjecture of Erdős
• Judicious partitions of hypergraphs
• Maximum cuts and judicious partitions in graphs without short cycles
• Judicious partitions of 3-uniform hypergraphs
• Exact bounds for judicious partitions of graphs
• Weighted sums of certain dependent random variables
• Problems and results on judicious partitions
• Probability Inequalities for Sums of Bounded Random Variables
• Some Extremal Properties of Bipartite Subgraphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item