Lower Bounds for Maximum Weighted Cut
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917744815898624 |
|---|---|
| author | Gutin, Gregory Yeo, Anders |
| author_facet | Gutin, Gregory Yeo, Anders |
| contents | While there have been many results on lower bounds for Max Cut in unweighted graphs, there are only few results for lower bounds for Max Cut in weighted graphs. 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, 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2104_05536 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Lower Bounds for Maximum Weighted Cut Gutin, Gregory Yeo, Anders Combinatorics Discrete Mathematics While there have been many results on lower bounds for Max Cut in unweighted graphs, there are only few results for lower bounds for Max Cut in weighted graphs. 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, 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. |
| title | Lower Bounds for Maximum Weighted Cut |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2104.05536 |