Lower Bounds for Maximum Weight Bisections of Weighted Triangle‐Free Subcubic Graphs
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).
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}
}
EUVIMED