Bisections of graphs

DOI10.1016/j.jctb.2013.06.002zbMath1301.05266arXiv1109.3180OpenAlexW2110869621MaRDI QIDQ461728

Po-Shen Loh, Choongbum Lee, Benjamin Sudakov

Publication date: 13 October 2014

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

Full work available at URL: https://arxiv.org/abs/1109.3180

zbMATH Keywords

Edwards bound on maximum cuts

Mathematics Subject Classification ID

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

Related Items (26)

On judicious partitions of uniform hypergraphs ⋮ On judicious partitions of graphs ⋮ Judicious bisection of hypergraphs ⋮ Maximum bisections of graphs without cycles of length 4 ⋮ 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 ⋮ On judicious bisections of graphs ⋮ Graph partitioning: an updated survey ⋮ On tight components and anti-tight components ⋮ Bisections of Graphs Without Short Cycles ⋮ 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 ⋮ Maximum bisections of graphs without short even cycles ⋮ On splitting digraphs ⋮ On bipartitions of directed graphs with small semidegree ⋮ On minimum balanced bipartitions of triangle-free graphs ⋮ Max-bisections of \(H\)-free graphs ⋮ Bipartitions of oriented graphs ⋮ Bipartition of graph under degree constraints ⋮ A bound on judicious bipartitions of directed graphs ⋮ On a Problem of Judiciousk-Partitions of Graphs ⋮ On bisections of directed graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On several partitioning problems of Bollobás and Scott
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Partitioning 3-uniform hypergraphs
• Max \(k\)-cut and judicious \(k\)-partitions
• Triangle-free partial graphs and edge covering theorems
• The size of the largest bipartite subgraphs
• Maximum cuts and judicious partitions in graphs without short cycles
• Judicious partitions of 3-uniform hypergraphs
• Exact bounds for judicious partitions of graphs
• The Bollobás-Thomason conjecture for \(3\)-uniform hypergraphs
• Maximumk-colorable subgraphs
• Bipartite Subgraphs of Triangle-Free Graphs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Judicious partitions of bounded‐degree graphs
• Gadgets, Approximation, and Linear Programming
• Problems and results on judicious partitions
• Maximizing Several Cuts Simultaneously
• Some optimal inapproximability results
• The RPR2 rounding technique for semidefinite programs
• Some Extremal Properties of Bipartite Subgraphs

This page was built for publication: Bisections of graphs