Metraipolis › archive › dc_ab40ab4bf17d
Weighted Max Cut in Subcubic Graphs — arXiv:2611.05178
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05178
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T19:00:24.692Z
- SHA-256 of the archived text
5243d2a92aa6b566d49b806e00b70846a0379ca6dede696180591a6bdf69bc43- Stable URL of this page
https://metraipolis.com/documento/dc_ab40ab4bf17d
How to cite
Weighted Max Cut in Subcubic Graphs — arXiv:2611.05178 — arXiv (en), https://arxiv.org/abs/2611.05178 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ab40ab4bf17d (Metraipolis archive dc_ab40ab4bf17d, sha256 5243d2a92aa6b566d49b806e00b70846a0379ca6dede696180591a6bdf69bc43)
BibTeX
@misc{dcab40ab4bf17d,
title = {Weighted Max Cut in Subcubic Graphs — arXiv:2611.05178},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05178},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ab40ab4bf17d; sha256 5243d2a92aa6b566d49b806e00b70846a0379ca6dede696180591a6bdf69bc43},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05178. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
For a graph $G$ with nonnegative edge weights, let $\operatorname{mc}(G,w)$ denote the maximum total weight of a cut and let $w(G)$ denote the total edge weight. We prove that every edge-weighted triangle-free subcubic graph satisfies $\operatorname{mc}(G,w)\geq \frac{15}{19}w(G)$, improving the bound of $\frac{8}{11}$ due to Gutin and Yeo. For subcubic graphs of odd girth at least seven and nine, we strengthen this bound to $\frac{47}{59}w(G)$ and $\frac45w(G)$, respectively, establishing the conjecture of Gutin and Yeo for graphs of odd girth at least nine. Our proofs combine structural properties of vertex partitions with randomized cut constructions and convex combinations of the resulting bounds.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.05178 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T18:38:22.325Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).