Problems and results on judicious partitions

DOI10.1002/rsa.10062zbMath1013.05059OpenAlexW1578444888MaRDI QIDQ4798176

Béla Bollobás, Alexander D. Scott

Publication date: 19 March 2003

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10062

zbMATH Keywords

judicious partitionpartitioning graphslargest bipartite subgraphpartitioning hypergraphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (70)

On judicious partitions of uniform hypergraphs ⋮ Minimum degree thresholds for bipartite graph tiling ⋮ On judicious partitions of graphs ⋮ Judicious bisection of hypergraphs ⋮ Judicious partitions of weighted hypergraphs ⋮ Biased partitions and judicious \(k\)-partitions of graphs ⋮ Maximum bisections of graphs without cycles of length 4 ⋮ On judicious bipartitions of directed graphs ⋮ Judicious partitions of directed graphs ⋮ On several partitioning problems of Bollobás and Scott ⋮ Bounds for pairs in judicious partitioning of graphs ⋮ Friendly bisections of random graphs ⋮ Partitioning digraphs with outdegree at least 4 ⋮ On bisections of graphs without complete bipartite graphs ⋮ On judicious bisections of graphs ⋮ Upper bounds on minimum balanced bipartitions ⋮ Graph partitioning: an updated survey ⋮ On a bipartition problem of Bollobás and Scott ⋮ On tight components and anti-tight components ⋮ Extremal problems in hypergraph colourings ⋮ Bisections of Graphs Without Short Cycles ⋮ Partitioning dense uniform hypergraphs ⋮ Optimal bisections of directed graphs ⋮ Graph partitions under average degree constraint ⋮ Defective coloring of hypergraphs ⋮ The Bollobás--Scott Conjecture for 4-Uniform Hypergraphs ⋮ Judicious Partitioning of Hypergraphs with Edges of Size at Most 2 ⋮ Degree conditions for the existence of vertex-disjoint cycles and paths: a survey ⋮ Maximum cuts of graphs with forbidden cycles ⋮ Bisections of graphs ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ A bound for judicious \(k\)-partitions of graphs ⋮ The Bollobás-Thomason conjecture for \(3\)-uniform hypergraphs ⋮ Maximum cuts in \(\mathscr{H} \)-free graphs ⋮ Maximum bisections of graphs without short even cycles ⋮ Judicious partitions of uniform hypergraphs ⋮ Bisections of graphs without \(K_{2, l}\) ⋮ On splitting digraphs ⋮ Graphic Sequences Have Realizations Containing Bisections of Large Degree ⋮ Bounds for judicious balanced bipartitions of graphs ⋮ Triangle-free subcubic graphs with minimum bipartite density ⋮ On bipartitions of directed graphs with small semidegree ⋮ On minimum balanced bipartitions of triangle-free graphs ⋮ A note on balanced bipartitions ⋮ An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance ⋮ Bounds for pairs in partitions of graphs ⋮ Max \(k\)-cut and judicious \(k\)-partitions ⋮ Simple probabilistic analysis to generalize bottleneck graph multi-partitioning ⋮ On judicious bipartitions of graphs ⋮ Minimum balanced bipartitions of planar triangulations ⋮ Bipartitions of oriented graphs ⋮ Better Bounds for k-Partitions of Graphs ⋮ On balanced bipartitions of graphs ⋮ Bipartition of graph under degree constraints ⋮ Judicious \(k\)-partitions of graphs ⋮ On partitions of \(K_{2, 3}\)-free graphs under degree constraints ⋮ MAXIMUM CUTS IN GRAPHS WITHOUT WHEELS ⋮ A bound on judicious bipartitions of directed graphs ⋮ BIPARTITE SUBGRAPHS OF -FREE GRAPHS ⋮ On a Problem of Judiciousk-Partitions of Graphs ⋮ Internal Partitions of Regular Graphs ⋮ Bipartite density of triangle-free subcubic graphs ⋮ Partitioning 3-uniform hypergraphs ⋮ Judicious partitions of bounded‐degree graphs ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Maximum bipartite subgraphs in graphs without short cycles ⋮ On problems about judicious bipartitions of graphs ⋮ Maximum bipartite subgraphs in $H$-free graphs ⋮ On judicious partitions of hypergraphs with edges of size at most 3 ⋮ On bisections of directed graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a theorem about vertex colorings of graphs
• Unfriendly partitions of a graph
• How to make a graph bipartite
• On a bottleneck bipartition conjecture of Erdős
• On an upper bound of the graph's chromatic number, depending on the graph's degree and density
• Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
• Judicious partitions of graphs
• Judicious partitions of hypergraphs
• Bipartite subgraphs of integer weighted graphs
• Judicious partitions of 3-uniform hypergraphs
• Exact bounds for judicious partitions of graphs
• On some extremal problems in graph theory
• Weighted sums of certain dependent random variables
• Bipartite subgraphs
• Largest bipartite subgraphs in triangle-free graphs with maximum degree three
• Maximumk-colorable subgraphs
• Extremal bipartite subgraphs of cubic triangle-free graphs
• A note on bipartite subgraphs of triangle‐free graphs
• Bipartite Subgraphs of Triangle-Free Graphs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Judicious partitions of bounded‐degree graphs
• Probability Inequalities for Sums of Bounded Random Variables
• Über die Approximation von Zahlen durch Reihen mit positiven Gliedern
• Some Extremal Properties of Bipartite Subgraphs

This page was built for publication: Problems and results on judicious partitions