Sharp lower bounds for bisections of graphs with bounded maximum degree

@misc{guo2026sharp,
  title = {{Sharp lower bounds for bisections of graphs with bounded maximum degree}},
  author = {Qiwen Guo and Gregory Gutin},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.15024},
  eprint = {2610.15024},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.15024},
  note = {CC BY 4.0},
}

TY  - UNPB
TI  - Sharp lower bounds for bisections of graphs with bounded maximum degree
AU  - Qiwen Guo
AU  - Gregory Gutin
PY  - 2026
DA  - 2026/10/10
PB  - arXiv
DO  - 10.48550/arxiv.2610.15024
UR  - https://arxiv.org/abs/2610.15024
AB  - A bisection of a graph is a partition of its vertex set into two parts whose sizes differ by at most one. We prove that every graph with m edges and maximum degree at most k has a bisection of size at least (k+1)/2km when k is odd, and at least (k+2)/(2(k+1))m when k is even. Both bounds are sharp, with equality for complete graphs. This establishes the unweighted case of the bisection conjecture of Gerke, Gutin, Yeo and Zhou (arXiv 2024), removes the additive error from the corresponding bounds of Lee, Loh and Sudakov (JCTB 2013), and extends the odd-degree regular case proved by Bollobás and Scott (JGT 2004) to arbitrary graphs of bounded maximum degree. The proof combines the matching-and-pairing method with the Gallai--Edmonds decomposition. Hall's theorem controls the number of uncovered factor-critical components whose internal degrees are all even. A boundary-edge count bounds this obstruction by the total degree deficiency, while the remaining uncovered components supply the required pairing gain.
ER  -