Lower Bounds for Maximum Weighted Cut

Gregory Gutin*, Anders Yeo

*Kontaktforfatter

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Abstract

While there have been many results on lower bounds for Max Cut in unweighted graphs, the only lower bound for noninteger weights is that by Poljak and Turzík [Discrete Math., 58 (1986), pp. 99-104]. In this paper, we launch an extensive study of lower bounds for Max Cut in weighted graphs. We introduce a new approach for obtaining lower bounds for Weighted Max Cut. Using it, the probabilistic method, Vizing's chromatic index theorem, and other tools, we obtain several lower bounds for arbitrary weighted graphs, weighted graphs of bounded girth, and triangle-free weighted graphs. We pose conjectures and open questions.

OriginalsprogEngelsk
TidsskriftSIAM Journal on Discrete Mathematics
Vol/bind37
Udgave nummer2
Sider (fra-til)1142-1161
Antal sider20
ISSN0895-4801
DOI
StatusUdgivet - 2023

Bibliografisk note

Publisher Copyright:
Copyright © by SIAM.

Fingeraftryk

Dyk ned i forskningsemnerne om 'Lower Bounds for Maximum Weighted Cut'. Sammen danner de et unikt fingeraftryk.

Citationsformater