EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Lower Bounds for Maximum Weight Bisections of Weighted Triangle‐Free Subcubic Graphs

Stefanie Gerke, Gregory Gutin, Anders Yeo, Yacong Zhou

Journal of Graph Theory · 2026-10 · 113 (2) · 252-273

DOI: 10.1002/jgt.70056 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 14.05.2026. Verfasst von Stefanie Gerke und 3 weiteren Autor:innen. Die Arbeit nennt 15 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A bisection of a graph is a cut in which the number of vertices in the two parts of the cut differ by at most 1. In this paper, we consider maximum weight bisections of edge‐weighted triangle‐free subcubic graphs and show that every weighted triangle‐free subcubic graph has a bisection with weight at least unless (where ). We conjecture that can be replaced by , the value of for the Peterson graph and prove the conjecture for weighted bridgeless triangle‐free cubic graphs.

Zitieren

APA

Gerke, S., Gutin, G., Yeo, A., & Zhou, Y. (2026). Lower Bounds for Maximum Weight Bisections of Weighted Triangle‐Free Subcubic Graphs. Journal of Graph Theory, 113(2), 252-273. https://doi.org/10.1002/jgt.70056

Vancouver

Gerke S, Gutin G, Yeo A, Zhou Y. Lower Bounds for Maximum Weight Bisections of Weighted Triangle‐Free Subcubic Graphs. Journal of Graph Theory. 2026;113(2):252-273. doi:10.1002/jgt.70056

BibTeX
@article{Gerke2026,
  author = {Gerke, Stefanie and Gutin, Gregory and Yeo, Anders and Zhou, Yacong},
  title = {Lower Bounds for Maximum Weight Bisections of Weighted Triangle‐Free Subcubic Graphs},
  journal = {Journal of Graph Theory},
  year = {2026},
  volume = {113},
  number = {2},
  pages = {252--273},
  doi = {10.1002/jgt.70056}
}
Kostenlos starten →