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).