Bisections of graphs

DOI10.1016/J.JCTB.2013.06.002zbMATH Open1301.05266arXiv1109.3180OpenAlexW2110869621MaRDI QIDQ461728FDOQ461728

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)

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.

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

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

zbMATH Keywords

Edwards bound on maximum cuts

Mathematics Subject Classification ID

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

Cites Work

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

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
• Cutting a graph into two dissimilar halves
• On judicious partitions of graphs
• Friendly bisections of random graphs
• On bipartitions of directed graphs with small semidegree
• Title not available (Why is that?)
• Judicious bisection of hypergraphs
• Note on maximal bisection above tight lower bound
• Graph partitioning: an updated survey
• Bipartitions of oriented graphs
• Title not available (Why is that?)
• Maximum bisections of graphs without cycles of length 4
• 10 problems for partitions of triangle-free graphs
• Max-bisections of \(H\)-free graphs
• A bound on judicious bipartitions of directed graphs
• Bisection width of transposition graphs
• Bisection envelopes
• Optimal bisections of directed graphs
• Judicious partitioning of hypergraphs with edges of size at most 2
• Bisections of graphs without short cycles
• On tight components and anti-tight components
• On minimum balanced bipartitions of triangle-free graphs
• 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)