Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 15 min ago
PreprintCC BY 4.0arXiv

Weighted Max Cut in Subcubic Graphs

  • Will Hausmann
Open at sourcePDFDOICite

Abstract

For a graph G with nonnegative edge weights, let 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 mc(G,w)≥ 15/19w(G), improving the bound of 8/11 due to Gutin and Yeo. For subcubic graphs of odd girth at least seven and nine, we strengthen this bound to 47/59w(G) and 4/5w(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.

Related

  1. Packing colourings of claw-free subcubic graphs
    Federico Romaniello
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Rich-neighbor 5-edge-colorings of subcubic graphs whose 3-vertices induce a matching
    Jiangxu Kong, Zhuming Lin, Yan Wang
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. On (1,24) and (1,25)-packing edge-coloring of sparse subcubic graphs
    Seog-Jin Kim, Xujun Liu, Boyan Xu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Nadler Theorem on Generalized Metric Spaces with Weighted Graphs
    Ismat Beg, Muhammad Aslam Javed
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsarXiv
  5. Flow decomposition and stochastic completeness of weighted graphs
    Qingsong Gu, Lu Hao, Xueping Huang +1
    arXivPreprintarXiv licenceFull textAnalysis & PDEsGeometry & topologyarXiv

Cite

BibTeXRIS
BibTeX
@misc{hausmann2026weighted,
  title = {{Weighted Max Cut in Subcubic Graphs}},
  author = {Will Hausmann},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.05178},
  eprint = {2611.05178},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.05178},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Weighted Max Cut in Subcubic Graphs
AU  - Will Hausmann
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.05178
UR  - https://arxiv.org/abs/2611.05178
AB  - For a graph G with nonnegative edge weights, let 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 mc(G,w)≥ 15/19w(G), improving the bound of 8/11 due to Gutin and Yeo. For subcubic graphs of odd girth at least seven and nine, we strengthen this bound to 47/59w(G) and 4/5w(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.
ER  -