Bisections of graphs

DOI10.1016/J.JCTB.2013.06.002MaRDI QIDQ461728zbMATH OpenOpenAlexFDO

Authors Choongbum Lee, Po-Shen Loh, Benny 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)

Abstract: A bisection of a graph is a bipartition of its vertex set in which the number of vertices in the two parts differ by at most 1, and its size is the number of edges which go across the two parts. In this paper, motivated by several questions and conjectures of Bollob'as and Scott, we study maximum bisections of graphs. First, we extend the classical Edwards bound on maximum cuts to bisections. A simple corollary of our result implies that every graph on $n$ vertices and $m$ edges with no isolated vertices, and maximum degree at most $n/3+1$, admits a bisection of size at least $m/2+n/6$. Then using the tools that we developed to extend Edwards's bound, we prove a judicious bisection result which states that graphs with large minimum degree have a bisection in which both parts span relatively few edges. A special case of this general theorem answers a conjecture of Bollob'as and Scott, and shows that every graph on $n$ vertices and $m$ edges of minimum degree at least 2 admits a bisection in which the number of edges in each part is at most $(1/3+o(1))m$. We also present several other results on bisections of graphs.

Recommendations

• On judicious bisections of graphs
• On bisections of graphs without complete bipartite graphs
• Bisections of graphs without \(K_{2, l}\)
• Maximum bisections of graphs without short even cycles
• Bisections of graphs without short cycles

Cites work

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

Cited in

(39)

• Maximum bisections of graphs without short even cycles
• On bisections of graphs without complete bipartite graphs
• Graph bisection revisited
• On judicious partitions of uniform hypergraphs
• On judicious bisections of graphs
• On judicious partitions of graphs
• Cutting a graph into two dissimilar halves
• On bipartitions of directed graphs with small semidegree
• Friendly bisections of random graphs
• Judicious bisection of hypergraphs
• Note on maximal bisection above tight lower bound
• scientific article; zbMATH DE number 1905103 (Why is no real title available?)
• Bipartitions of oriented graphs
• Graph partitioning: an updated survey
• scientific article; zbMATH DE number 4093513 (Why is no real title available?)
• Maximum bisections of graphs without cycles of length 4
• Max-bisections of \(H\)-free graphs
• A bound on judicious bipartitions of directed graphs
• Bisection width of transposition graphs
• 10 problems for partitions of triangle-free graphs
• Bisection envelopes
• Optimal bisections of directed graphs
• On tight components and anti-tight components
• Bisections of graphs without short cycles
• On minimum balanced bipartitions of triangle-free graphs
• Judicious partitioning of hypergraphs with edges of size at most 2
• Maximum bisections of graphs with girth at least six
• On judicious bipartitions of directed graphs
• On bisections of directed graphs
• Maximum bisections of graphs without cycles of length four and five
• Partitioning digraphs with outdegree at least 4
• The Bollobás-Scott conjecture for 4-uniform hypergraphs
• On splitting digraphs
• Bipartition of graph under degree constraints
• Bounds for pairs in judicious partitioning of graphs
• A note on judicious bisections of graphs
• Judicious partitions of directed graphs
• On a problem of judicious \(k\)-partitions of graphs
• Weak external bisections of regular graphs

This page was built for publication: Bisections of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q461728)