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

• Bipartite Subgraphs of Triangle-Free Graphs
• Exact bounds for judicious partitions of graphs
• Gadgets, Approximation, and Linear Programming
• 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?)
• 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

(44)

• Bisection width of transposition graphs
• Graph bisection revisited
• Note on maximal bisection above tight lower bound
• On splitting digraphs
• On bipartitions of directed graphs with small semidegree
• On minimum balanced bipartitions of triangle-free graphs
• Maximum bisections of graphs without cycles of length 4
• On judicious bipartitions of directed graphs
• Maximum bisections of graphs without short even cycles
• Max-bisections of \(H\)-free graphs
• A bound on judicious bipartitions of directed graphs
• Bisection envelopes
• On bisections of directed graphs
• Bipartition of graph under degree constraints
• On judicious partitions of uniform hypergraphs
• On judicious partitions of graphs
• Judicious bisection of hypergraphs
• Bounds for pairs in judicious partitioning of graphs
• Judicious partitions of directed graphs
• Cutting a graph into two dissimilar halves
• scientific article; zbMATH DE number 4093513 (Why is no real title available?)
• On judicious bisections of graphs
• Bisections of graphs without short cycles
• The Bollobás-Scott conjecture for 4-uniform hypergraphs
• scientific article; zbMATH DE number 1905103 (Why is no real title available?)
• On a problem of judicious k-partitions of graphs
• Judicious partitioning of hypergraphs with edges of size at most 2
• Friendly bisections of random graphs
• 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
• Weak external bisections of regular graphs
• 10 problems for partitions of triangle-free graphs
• Maximum bisections of graphs with girth at least six
• Maximum bisections of graphs without cycles of length four and five
• A note on judicious bisections of graphs
• Minimum bisections of graphs without even cycles
• On min-bisections of graphs
• Bisections of directed graphs without complete bipartite subgraphs
• On maximum bisections of \(\{C_4, \theta (2, 3, 3)\}\)-free graphs
• Bipartitions of oriented graphs
• An improved SDP rounding approximation algorithm for the max hypergraph bisection
• On tight components and anti-tight components

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)