Lower Bounds for Maximum Weighted Cut

Gregory Gutin*, Anders Yeo


Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review


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.

TidsskriftSIAM Journal on Discrete Mathematics
Udgave nummer2
Sider (fra-til)1142-1161
Antal sider20
StatusUdgivet - 2023

Bibliografisk note

Publisher Copyright:
Copyright © by SIAM.


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