On judicious bisections of graphs

DOI10.1016/j.jctb.2014.01.004zbMath1297.05194MaRDI QIDQ402590

Xingxing Yu, Bao-Gang Xu

Publication date: 28 August 2014

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.2014.01.004

zbMATH Keywords

judicious partition; balanced partition

Mathematics Subject Classification ID

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

Related Items

Bisections of Graphs Without Short Cycles, The Bollobás--Scott Conjecture for 4-Uniform Hypergraphs, On a Problem of Judiciousk-Partitions of Graphs, Balanced Judicious Bipartition is Fixed-Parameter Tractable, Balanced Judicious Bipartition is Fixed-Parameter Tractable, Judicious Partitioning of Hypergraphs with Edges of Size at Most 2, Partitioning digraphs with outdegree at least 4, On bisections of graphs without complete bipartite graphs, Graph partitioning: an updated survey, Optimal bisections of directed graphs, On judicious partitions of uniform hypergraphs, On judicious partitions of graphs, Judicious partitions of weighted hypergraphs, Bipartitions of oriented graphs, Partitioning dense uniform hypergraphs, Bisections of graphs without \(K_{2, l}\), Bounds for judicious balanced bipartitions of graphs, On partitions of \(K_{2, 3}\)-free graphs under degree constraints, On bipartitions of directed graphs with small semidegree, An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance, Maximum bipartite subgraphs in graphs without short cycles, On judicious bipartitions of directed graphs, Maximum cuts in \(\mathscr{H} \)-free graphs, Max-bisections of \(H\)-free graphs, On bisections of directed graphs, Bipartition of graph under degree constraints, Biased partitions and judicious \(k\)-partitions of graphs, Bounds for pairs in judicious partitioning of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Bisections of graphs
• A note on balanced bipartitions
• Max \(k\)-cut and judicious \(k\)-partitions
• Judicious \(k\)-partitions of graphs
• On a bottleneck bipartition conjecture of Erdős
• Maximum cuts and judicious partitions in graphs without short cycles
• Exact bounds for judicious partitions of graphs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Judicious partitions of bounded‐degree graphs
• Problems and results on judicious partitions
• Reducibility among Combinatorial Problems
• Balanced judicious bipartitions of graphs
• Better Bounds for k-Partitions of Graphs
• Node-and edge-deletion NP-complete problems
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• The RPR2 rounding technique for semidefinite programs
• Some Extremal Properties of Bipartite Subgraphs